运行时错误在python：“最大递归深度超过”

Question

我有一个程序，通过它表示像这样一个迷宫二维列表搜索：

#################################### 
#S# ## ######## # #  #  # # 
# # #    # #  # # 
# # ##### ## ###### # ####### # # 
### # ## ##  # # #  #### # 
# # # ####### # ### #E# 
#################################### 

我明白了一个递归错误是什么，但我不知道为什么这个代码会导致它，因为它应该简单地导致找到“E”。有谁知道这可能会产生错误？

def solve(x,y): 
    mazeList = loadMaze("sample.maze")  

    if mazeList[y][x] == "E": 
     return "YOU'VE SOLVED THE MAZE!" 
    elif mazeList[y][x+1] == " ": #right 
     mazeList[y][x+1] = ">" 
     solve(x+1,y) 
    elif mazeList[y+1][x] == " ": #down 
     mazeList[y+1][x] = "v" 
     solve(x,y+1)  
    elif mazeList[y][x-1] == " ": #left 
     mazeList[y][x-1] = "<" 
     solve(x-1,y)  
    elif mazeList[y-1][x] == " ": #up 
     mazeList[y-1][x] = "^" 
     solve(x,y-1)  

Answer 1

您重新加载每次调用该函数时间mazeList。

因此，在solve()开始时，您已经回到了初始条件，最终以圆圈运行。

使用关键字参数来传递mazeList到递归调用，它默认为None，当它仍然是None只加载迷宫：

def solve(x, y, mazeList=None): 
    if mazeList is None: 
     mazeList = loadMaze("sample.maze") 

，并通过mazeList到递归调用。

接下来的问题是，你永远不会返回递归调用;当你从内solve()你仍然需要返回其结果调用solve()：

def solve(x, y, mazeList=None): 
    if mazeList is None: 
     mazeList = loadMaze("sample.maze") 

    if mazeList[y][x] == "E": 
     return "YOU'VE SOLVED THE MAZE!" 
    elif mazeList[y][x+1] == " ": #right 
     mazeList[y][x+1] = ">" 
     return solve(x+1,y,mazeList) 
    elif mazeList[y+1][x] == " ": #down 
     mazeList[y+1][x] = "v" 
     return solve(x,y+1,mazeList)  
    elif mazeList[y][x-1] == " ": #left 
     mazeList[y][x-1] = "<" 
     return solve(x-1,y,mazeList)  
    elif mazeList[y-1][x] == " ": #up 
     mazeList[y-1][x] = "^" 
     return solve(x,y-1,mazeList)  

你还是会画自己在使用这种技术一角落;要递归地解决迷宫问题，你需要尝试所有的路径，而不仅仅是一个，并且给每个递归调用一个拷贝迷宫与一个被选择的路径标记出来。

您也一直在测试下一个单元格，但从未考虑到下一个单元格可能是目标;你永远不会移动到E，因为该单元不等于' '，所以它不是移动候选。

以下版本可以解决您的迷宫：

directions = (
    (1, 0, '>'), 
    (0, 1, 'v'), 
    (-1, 0, '<'), 
    (0, -1, '^'), 
) 

def solve(x, y, mazeList=None): 
    if mazeList is None: 
     mazeList = loadMaze("sample.maze") 

    for dx, dy, char in directions: 
     nx, ny = x + dx, y + dy 

     if mazeList[ny][nx] == "E": 
      return "YOU'VE SOLVED THE MAZE!" 

     if mazeList[ny][nx] == " ": 
      new_maze = [m[:] for m in mazeList] 
      new_maze[ny][nx] = char 
      result = solve(nx, ny, new_maze) 
      if result is not None: 
       return result 

测试每个方向分别是越来越繁琐，所以我取代了一个遍历的方向，而不是一个序列;每个元组都是x，y中的变化以及在该方向上移动时使用的字符。

演示，与解决迷宫的打印输出：

>>> def loadMaze(ignored): 
...  maze = '''\ 
... #################################### 
... #S# ## ######## # #  #  # # 
... # # #    # #  # # 
... # # ##### ## ###### # ####### # # 
... ### # ## ##  # # #  #### # 
... # # # ####### # ### #E# 
... #################################### 
... ''' 
...  return [list(m) for m in maze.splitlines()] 
... 
>>> directions = (
...  (1, 0, '>'), 
...  (0, 1, 'v'), 
...  (-1, 0, '<'), 
...  (0, -1, '^'), 
...) 
>>> 
>>> def solve(x, y, mazeList=None): 
...  if mazeList is None: 
...   mazeList = loadMaze("sample.maze") 
...  for dx, dy, char in directions: 
...   nx, ny = x + dx, y + dy 
...   if mazeList[ny][nx] == "E": 
...    print '\n'.join([''.join(m) for m in mazeList]) 
...    return "YOU'VE SOLVED THE MAZE!" 
...   if mazeList[ny][nx] == " ": 
...    new_maze = [m[:] for m in mazeList] 
...    new_maze[ny][nx] = char 
...    result = solve(nx, ny, new_maze) 
...    if result is not None: 
...     return result 
... 
>>> solve(1, 1) 
#################################### 
#S# ## ######## # #^>>>>># ^>># # 
#v#^>># ^>>>  #^# v>>>>#v>># 
#v>>#v#####^##v######^# ####### #v# 
### #v##^>>>##v>>>>>#^# #  ####v# 
# #v>>># #######v>># ### #E# 
#################################### 
"YOU'VE SOLVED THE MAZE!"