为什么这个递归程序的行为很奇怪

Question

我正在写一个简单的递归函数，它取一个正方形矩阵、起始位置坐标和起始位置的值，然后找出是否有一条到正方形矩阵右下角的路径。规则是从起始位置开始向右或向下移动，当下一个位置的值小于或等于当前值时，您可以移动并更新两者之和的值，依此类推。如果存在，则返回True和路径，如果不存在，则返回False和[]。下面是我写的程序

def find_path(matrix, x, y, value):
length = len(matrix)
if x == y == (length-1):
return (True,[(x,y)])
# Go down and search
if x < length -1 and matrix[x+1][y] <= value:
hasSolution,solution = find_path(matrix, x+1, y, value + matrix[x+1][y])
if hasSolution:
solution.append((x,y))
return solution

# If the road below is not feasible, take the right
if y < length -1 and matrix[x][y+1] <= value:
hasSolution,solution = find_path(matrix, x, y+1, value + matrix[x][y+1])
if hasSolution:
solution.append((x,y))
return solution

# If neither left nor right, it means there is no solution
return (False,[])

然而，当我输入[[76,13]，[40,42]]时，python解释器返回

File "/Users/zg/PycharmProjects/z/main.py", line 42, in find_path
solution.append((x,y))
AttributeError: 'tuple' object has no attribute 'append'

为什么会出现这种结果？

Answer 1

从错误中可以看出，solution是tuple，tuples是不可变的，当然没有append方法。

solution是在您发布的代码片段之外定义的，因此它必须是全局变量或在find_path之外的包装函数中。如果要对其append，则list将是正确的数据结构。

此外，return (True,[(x,y)])没有多大意义，因为当您找到有效路径时，x和y将始终是length-1，所以我会重新考虑代码的这一部分。