增加python递归限制后,程序崩溃。为什么?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (152)

一直在试图用回溯来解决迷宫问题。该代码使用多个递归:

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崩溃了。发生什么事?我该如何解决这个问题?

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

*稍后添加:在solve_maze定义的末尾有这段代码:

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

我注意到通过删除它,该程序运行良好。仍然不知道为什么

提问于
用户回答回答于

我收集的信息如下:

  1. 问题是由于堆栈溢出。
  2. 不建议编辑此限制。
  3. 默认的递归深度限制是相当大的,如果程序一直超出限制,这是一个迹象表明代码有一些错误。
  4. 该定义中if solve_maze(x, y):的陈述是solve_maze无限递归的原因。
用户回答回答于

填写你的代码的缺失部分,它似乎工作:

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]]

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励