增加 python 递归限制后，程序似乎崩溃了。为什么？

Question

我一直在尝试使用回溯法解决迷宫问题。该代码使用了多个递归：

def solve_maze(x,y):    
        if maze[x][y] == 'G': #checking if we've reached the target
            solution[x][y] = 1
            return True
        if x>=0 and y>=0 and x<length and y<width and solution[x][y] == 0 and maze[x][y] == ' ':
            solution[x][y] = 1
            if solve_maze(x+1, y):
                return True
            if solve_maze(x, y+1):
                return True
            if solve_maze(x-1, y):
                return True
            if solve_maze(x, y-1):
                return True
            solution[x][y] = 0
            return False

我第一次执行程序时，出现 "recursion limit exceeded" 错误。为了解决这个问题，我增加了限制：

sys.setrecursionlimit(10000)

现在我运行程序 Python 崩溃了。怎么了？我该如何解决这个问题？迷宫不是很大。它的尺寸是 10*9:

maze = [['#'] * 10,
        ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', ' ', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#'],
        ['#', ' ', '#', '#', '#', '*', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#'],
        ['G', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#'] * 10]

*这是后来添加的：在solve_maze定义的末尾有这段代码：

if solve_maze(x, y):
        for i in solution:
            print(i)
    else:
        print('no solution')

我通过删除它注意到，该程序有效fine.Still不知道为什么

Answer 1

填写您的代码的缺失部分，似乎有效：

from pprint import pprint

maze = [['#'] * 10,
        ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', ' ', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', ' ', '#', '#'],
        ['#', ' ', '#', '#', '#', '*', '#', ' ', ' ', '#'],
        ['#', ' ', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],
        ['#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#'],
        ['G', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
        ['#'] * 10]

length = len(maze)
width = len(maze[0])
solution = [[0 for _ in range(width)] for _ in range(length)]


def solve_maze(x, y):
    if maze[x][y] == 'G':  # checking if we've reached the target
        solution[x][y] = 1
        return True
    if x >= 0 and y >= 0 and x < length and y < width and solution[x][y] == 0 and maze[x][y] in ' *':
        solution[x][y] = 1
        if solve_maze(x + 1, y):
            return True
        if solve_maze(x, y + 1):
            return True
        if solve_maze(x - 1, y):
            return True
        if solve_maze(x, y - 1):
            return True
        solution[x][y] = 0
        return False


solve_maze(4, 5)
pprint(solution)

我在 solve_maze 中所做的唯一更改是将 maze[x][y] == ' ' 更改为 maze[x][y] in ' *'，这样起始位置就不会破坏它。

输出：

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

如果您想知道您的代码有什么问题，您需要提供 MCVE。

Answer 2

我收集到的信息如下：

问题是由于堆栈溢出。
不建议编辑此限制。
默认的递归深度限制相当大，如果程序不断超过限制，则表明代码存在一些错误。
if solve_maze(x, y): 的语句在 solve_maze 定义体中是无限递归的原因。

综上所述，我发现问题是由于导致无限递归的错误造成的，程序运行良好，无需增加递归深度限制。

Answer 3

递归深度超过解决迷宫问题所需的深度。

最大递归深度不得比“到出口的路径长度”深很多。 路径的长度是 33（= 在到达出口之前在 10 * 9 地图中完成的步骤）。

如果迷宫有更多的分支，那么递归深度也会增加。然而，递归深度超过几千.

听起来不太合理

这有一个原因：您允许继续搜索到 相反的方向（搜索的来源）。这不是找到最短路径所必需的，如果你避免它，它会大大降低你的递归深度。

增加 python 递归限制后，程序似乎崩溃了。为什么？

After increasing python recursion limit, it seems like the program crashes. why?

python

recursion

maze

python-3.x