python中的运行时错误:“超出最大递归深度" [英] Runtime Error in python: "Maximum recursion depth exceeded"
问题描述
我有一个程序可以搜索代表迷宫的二维列表:
####################################S##############################################################################E###################################我明白什么是递归错误，但我不知道为什么这段代码会导致它，因为它应该只是导致找到E".有谁知道这可能如何产生错误?
defsolve(x,y):mazeList = loadMaze("sample.maze")如果 mazeList[y][x] == "E":你已经解决了迷宫！"elif mazeList[y][x+1] == " ": #right迷宫列表[y][x+1] = ">"解决(x+1,y)elif mazeList[y+1][x] == " ": #down迷宫列表[y+1][x] = "v"解决(x，y + 1)elif mazeList[y][x-1] == " ": #left迷宫列表[y][x-1] = "<"解决(x-1，y)elif mazeList[y-1][x] == " ": #up迷宫列表[y-1][x] = "^"解决(x，y-1)您每次调用函数时都会重新加载 mazeList .
所以在 solve() 开始时，你又回到了起始条件，你最终在循环中运行.
使用关键字参数将 mazeList 传递给递归调用，默认为 None 并且只在它仍然是 None 时加载迷宫:
def solve(x, y, mazeList=None):如果 mazeList 为 None:mazeList = loadMaze("sample.maze")并将 mazeList 传递给递归调用.
下一个问题是你永远不会返回递归调用；当您从 solve() 中调用 solve() 时，您仍然需要返回其结果:
def solve(x, y, mazeList=None):如果 mazeList 为 None:mazeList = loadMaze("sample.maze")如果 mazeList[y][x] == "E":你已经解决了迷宫！"elif mazeList[y][x+1] == " ": #right迷宫列表[y][x+1] = ">"返回解决(x + 1，y，迷宫列表)elif mazeList[y+1][x] == " ": #down迷宫列表[y+1][x] = "v"返回解决(x，y + 1，迷宫列表)elif mazeList[y][x-1] == " ": #left迷宫列表[y][x-1] = "<"返回解决(x-1，y，迷宫列表)elif mazeList[y-1][x] == " ": #up迷宫列表[y-1][x] = "^"返回解决(x，y-1，迷宫列表)你仍然会用这种技术把自己画在角落里；要递归解决迷宫，您需要尝试所有路径，而不仅仅是一个路径，并给每个递归调用一个副本迷宫，其中只标记出一条所选路径.
您也总是测试下一个单元格，但从不考虑下一个单元格可能是目标；你永远不会移动到 E 因为那个单元格不等于 ' '，所以它不是移动候选.
以下版本可以解决你的迷宫:
方向 = ((1, 0, '>'),(0, 1, 'v'),(-1, 0, '<'),(0, -1, '^'),)def解决(x，y，迷宫列表=无):如果 mazeList 为 None:mazeList = loadMaze("sample.maze")对于 dx, dy, char 方向:nx, ny = x + dx, y + dy如果 mazeList[ny][nx] == "E":你已经解决了迷宫！"如果 mazeList[ny][nx] == " ":new_maze = [m[:] for m in mazeList]new_maze[ny][nx] = 字符结果=解决(nx，ny，new_maze)如果结果不是无:返回结果单独测试每个方向变得很乏味，所以我用一系列方向上的循环代替了它；每个元组都是 x、y 和沿该方向移动时使用的字符的变化.
演示，打印出已解决的迷宫:
<预><代码>>>>def loadMaze(忽略):... 迷宫 = '''\... ##################################...#S################... ########...#########################...################... # # # ####### # ### #E#... ##################################...'''...返回 [list(m) for m in maze.splitlines()]...>>>方向 = (... (1, 0, '>'),... (0, 1, 'v'),... (-1, 0, '<'),... (0, -1, '^'),……)>>>>>>def解决(x，y，迷宫列表=无):...如果 mazeList 为 None:... mazeList = loadMaze("sample.maze")... 对于 dx, dy, char 方向:... nx, ny = x + dx, y + dy...如果 mazeList[ny][nx] == "E":... 打印 '\n'.join([''.join(m) for m in mazeList])...返回你已经解决了迷宫！"...如果 mazeList[ny][nx] == " ":... new_maze = [m[:] for m in mazeList]... new_maze[ny][nx] = char... 结果 = 解决(nx，ny，new_maze)...如果结果不是无:...返回结果...>>>解决(1, 1)###################################S#############^>>>>>#^>>###v#^>># ^>>>#^# v>>>>#v>>##v>>#v#####^##v######^# ########v#### #v##^>>>##v>>>>>#^# # ####v## #v>>># #######v>># ### #E###################################你已经解决了迷宫！"I have a program that searches through a 2D list that represents a maze like so:
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
I understand what a recursion error is but I don't know why this code causes it as it should simply lead to finding the "E". Does anyone know how this possibly generates the error?
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)
You re-load mazeList each time you call the function.
So at the start of solve() you are right back at the starting conditions, and you end up running in circles.
Use a keyword argument to pass mazeList on to recursive calls, default it to None and only load the maze when it is still None:
def solve(x, y, mazeList=None):
if mazeList is None:
mazeList = loadMaze("sample.maze")
and pass mazeList to recursive calls.
Next problem is that you never return recursive calls; when you call solve() from within solve() you still need to return its result:
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)
You'd still paint yourself in a corner with this technique; to recursively solve a maze, you need to try all paths, not just one, and give each recursive call a copy of the maze with the one chosen path marked out only.
You also always test for the next cell, but never take into account that that next cell could be the goal; you never move onto E because that cell is not equal to ' ', so it's not a move candidate.
The following version can solve your maze:
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
Testing for each direction separately was getting tedious, so I replaced that with a loop over a sequence of directions instead; each tuple is a change in x, in y and the character to use when moving in that direction.
Demo, with printout of the solved maze:
>>> 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!"
这篇关于python中的运行时错误:“超出最大递归深度"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
