使用递归回溯在python中生成迷宫时超过了最大递归深度

Question

我制作了一个程序，询问用户一个大小，并使用递归回溯算法生成一个大小为n^2的完美迷宫。我遇到了这个错误，看到我可以简单地使用：

sys.setrecursionlimit(8000)

它一开始运行得很好，但当我增加迷宫的大小时，我的python程序什么也没说就退出了。。。

这是我用来查方向的字典：

_dic = {
"N": (-1, 0),
"S": (1, 0),
"E": (0, 1),
"W": (0, -1),
}

我将迷宫存储在str的numpy数组中，我只存储迷宫中要修改的部分，并在将其转换为字符串时添加其余部分以供显示。例如，一个3(3x3(大小的迷宫在显示器上会是这样的：

.######
..#.#.#
#######
#.#.#.#
#######
#.#.#..
######.

但在我的阵列中，我只有中间部分：

.#.#.
#####
.#.#.
#####
.#.#.

这只是为了尝试优化一点。。。

这是实际的回溯功能：

# Recursive backtracking function that takes a posx and posy as position of the cell to visit
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal directions corresponding to valid neighbors if found such as ["N", "E"]
# if there si a valid neighbor on the right and beneath.
dir = self._hasNeighbors(posx, posy) 
lenght = len(dir)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return

# select a random direction to move to and remove it from the list
toBreak = dir.pop(dir.index(random.choice(dir)))
# Replace '#' by '.'
self._map[posx + self._dic[toBreak][0]][posy + self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx += self._dic[toBreak][0] * 2
posy += self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
self._backtrack(posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)

这是hasNeighbors一：

def _hasNeighbors(self, posx, posy):
result = []
# Checking neighbors in each direction
for dir in self._dic.keys():
# If the indexes doesn't exceed the size of the maze
if 0 <= posx + self._dic[dir][0] < self._size * 2 - 1 and 0 <= posy + self._dic[dir][1] < self._size * 2 - 1:
# If the neighbor hasn't been visited
if self._map[posx + self._dic[dir][0] * 2][posy + self._dic[dir][1] * 2] == '.':
#Append this direction to the list of valid neighbors
result.append(dir)
return result

对于像5、20、50这样的小尺寸来说，它就像一个魅力……但当我开始变大一点时，如果我不增加限制，我要么会有最大递归深度错误，如果我增加了限制，程序就会简单地退出，而不说这样的话：

PS C:UserspierrTravailCodeAmazing-Maze> python -m amazingmaze
Please entre the size of the maze : 100
PS C:UserspierrTravailCodeAmazing-Maze>

我真的不知道该怎么解决。我不明白为什么它会在这么小的尺寸下阻塞，我的意思是我应该能够在不流汗的情况下生成更大的尺寸。。。问题是我的递归回溯实现吗？我错过了什么吗？我的老师告诉我，这是因为我的停止状态不起作用，我可能正在访问我已经访问过的牢房，但我有点不同意，显然有什么问题，但我真的不认为是这样。您可以在上找到完整的代码https://github.com/lebair-pierre-alexis/Amazing-Maze

Answer 1

您的递归函数_backtrack适用于尾调用优化。尾调用优化允许无限递归(如果适用(。但是，由于Python的开发人员Guido van Rossum在这里解释的原因，Python并没有开箱即用。

• 但是，我们可以使用Chris Penner的方法添加它
  • 在函数定义中添加尾部递归装饰器
  • 使用递归函数的递归
• 使用这种方法，我可以修改github存储库中的代码，以运行大小为100的矩阵
• 下面的代码显示了您发布的代码所需的MOD

代码

# Tail recursion decorator (could place in file tail_recursion.py)
class Recurse(Exception):
def __init__(self, *args, **kwargs):
self.args = args
self.kwargs = kwargs
def recurse(*args, **kwargs):
raise Recurse(*args, **kwargs)

def tail_recursive(f):
def decorated(*args, **kwargs):
while True:
try:
return f(*args, **kwargs)
except Recurse as r:
args = r.args
kwargs = r.kwargs
continue
return decorated
# Recursive backtracking function that takes a posx and posy as position of the cell to visit
@tail_recursive  # add recursive decorator
def _backtrack(self, posx, posy):
self._map[posx][posy] = 'V' # Mark the cell as visited
while True:
# hasNeighbors returns a empty list if no valid neighbors ar found
# but returns a list of cardinal dir_ections corresponding to valid neighbors if found such as ["N", "E"]
# if there is a valid neighbor on the right and beneath.
dir_ = self._hasNeighbors(posx, posy)  # refactor dir to dir_ to avoid overwriting builtin function
lenght = len(dir_)
# If there is no valid neighbors this is a dead end then return to backtrack
if lenght == 0:
return

# select a random direction to move to and remove it from the list
toBreak = dir_.pop(dir_.index(random.choice(dir_)))
# Replace '#' by '.'
self._map[posx + self._dic[toBreak][0]][posy + self._dic[toBreak][1]] = '.'
# If there is only one valid neightbor break the wall and update posx and posy
# It uses the while loop to keep visiting cells without recursion as long as there is only one choice
if lenght == 1:
posx += self._dic[toBreak][0] * 2
posy += self._dic[toBreak][1] * 2
self._map[posx][posy] = 'V'
#recursive call of the backtrack function with the position of the cell we want to visit
else:
# Replace call with tail recursive call
# self._backtrack(posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)
recurse(self, posx + self._dic[toBreak][0] * 2, posy + self._dic[toBreak][1] * 2)