Maximum recursion depth exceeded when generating a maze in python with recursive backtracking-CodePudding

I made a program that ask the user a size and generate a perfect maze of size n^2 using the recursive backtarcking algorithm. I've run into this error and saw that i could simply use :

sys.setrecursionlimit(8000)

It worked well at the begining but when i increased the size of the maze my python program simply exited without saying anything...

Here is the dictionary i use to check directions :

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

I store the maze inside a numpy array of str, i only store the part of the maze that is going to be modified and add the rest for display when i convert it into a string. For instance a maze of size 3 (3x3) will look like this in display :

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

But in my array i'll only have the middle part :

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

This is just to try to optimize a bit...

Here is the actual backtracking function :

# 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)

And here is the hasNeighbors one :

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

It works like a charm for small sizes like 5, 20, 50... but when i start to go a bit bigger i either have the maximum recursion depth error if i don't increase the limit and if i do increase it the program simply exit without saying anything like this :

PS C:\Users\pierr\Travail\Code\Amazing-Maze> python -m amazingmaze
Please entre the size of the maze : 100
PS C:\Users\pierr\Travail\Code\Amazing-Maze>

I really don't know how to solve this. I don't understand why it blocks at such small sizes i mean i should be able to generate bigger size without breaking a sweat... Is it my recursive backtracking implementation that is the issue have i missed something ? My teacher told me that it was because my stopping condition wasn't working and i was probably visiting cells that i already visited but i kinda disagree, there is obviously something wrong but i really don't think it's that. You can find the complete code at https://github.com/lebair-pierre-alexis/Amazing-Maze

CodePudding user response：

Your recursive function _backtrack is suitable for Tail Call Optimization. Tail call optimization allows unlimited recursion (when applicable). But, Python does not have this out of the box for reasons explained here by Guido van Rossum, the developer of Python.

However, we can add it using a method by Chris Penner
- Add tail recursive decorator to function definition
- Recursion using recurse function
Using this approach I was able to modify your code in your github repository to run a matrix of size 100.
Code below shows needed mods to your posted code.

Code

# 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)