一旦达到目标，如何使我的递归算法停止？

Question

我正在尝试解决以下问题。

Find path for a robot in a maze from top left corner to bottom right corner.
The robot can move only to the right or bottom.
There are certain restricted areas where the robot cannot go into.

我的想法是先使用深度搜索，然后再右移，然后再向下。我的算法正在运行。但是我对递归感到非常生疏。我无法正确返回输出。这是我的代码

def robot_path(r, c, off_limits):
    """
    r -> number of rows in grid
    c -> number of columns in grid
    off_limits -> nested list containing positions of restricted areas
    """
    grid = list()
    for i in range(0, r):
        grid.append([1] * c)
    for off_limit in off_limits:
        grid[off_limit[0]][off_limit[1]] = 'X'
    path = list()
    return __move(grid, (0,0), path, (r-1, c-1))

def __move(grid, position, path, target):
    if position == target:
        return path
    x = position[0]
    y = position[1]
    if x < len(grid) and y < len(grid[0]):
        if grid[x][y] != 'X':
            path.append(1)
            __move(grid, (x, y+1), path, target)
            path.pop()
            path.append(0)
            __move(grid, (x+1, y), path, target)
            path.pop()

如何返回路径？在path列表中，0表示移动底部，1表示向右移动。但是，一旦到达右下角，我的算法就不会停止。它甚至在那之后运行，我得到一个None输出。一旦达到右下角，如何更改此设置以返回我的路径。

测试输出

robot_path(4, 4, [[0,2], [2,2], [3,0], [3, 1]])

应返回

[1, 0, 1, 1, 0, 0]

Answer 1

[不要简单给出答案，我建议考虑以下内容

• 第二个功能并非在所有路径中都具有return，仅在第一个if中具有>
• 递归函数通常不与可变对象结合在一起。您的路径对象使用pop()进行了突变。通常在递归函数中，如果仅传递和返回对象，而不是内联突变，则更加清楚。

例如：

def sum(l):
    if len(l) == 0:
        return 0
    return l[0] + sum(l[1:])
尾部传递给下一个函数，结果传递回链上。列表本身未在sum()函数中进行更改，只是为了向下传递而分成几部分。