運行時錯誤在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!"