直接返回递归函数与返回存储递归结果的变量为何结果不同？

以下两个DFS递归函数看似结构一致，但实际返回结果存在差异，核心原因是函数1的缩进错误导致关键代码未执行：

函数1（存在缩进问题） #

def DFS(r, c, grid):
   if (r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0])):
      return False
   if (grid[r][c] == 1):
      return True
      
      grid[r][c] = 1
      return DFS(r+1, c, grid) and DFS(r-1, c, grid) and DFS(r, c+1, grid) and DFS(r, c-1, grid)

函数2（缩进正确） #

def DFS(r, c, grid):
   if (r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0])):
      return False
   if (grid[r][c] == 1):
      return True
   grid[r][c] = 1

   down = DFS(r+1, c, grid)
   up = DFS(r-1, c, grid)
   right = DFS(r, c+1, grid)
   left = DFS(r, c-1, grid)
   return down and up and right and left

调用代码 #

for r in range(len(grid)):
    for c in range(len(grid[0])):
        if (grid[r][c] == 0):
            #print("searching", r, c)
            if (DFS(r, c, grid) == True):
                print([r,c])
                result += 1
return result

测试输入网格 #

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

差异原因分析 #

1. 函数1的致命缩进错误：
   函数1中，grid[r][c] = 1和后续的递归return语句被错误缩进在了if (grid[r][c] == 1): return True的代码块内部。

   • 当grid[r][c] == 1时，函数直接执行return True，后续代码完全不会运行；
   • 当grid[r][c] == 0时，不会进入该if分支，因此grid[r][c] = 1和递归遍历逻辑从未被执行，函数会走到末尾默认返回None。在布尔判断中None等价于False，所以函数1处理所有0值格子时，永远返回False。

2. 函数2的正确逻辑：
   函数2的代码缩进正确，当grid[r][c] == 0时，会先将当前格子标记为1（避免重复访问），再递归遍历上下左右四个方向，最后返回四个方向结果的逻辑与（只有所有方向都返回True时，函数才返回True）。

内容的提问来源于stack exchange，提问作者ML_201721