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

Question

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

Don't mess with `sys.setrecursionlimit`. It's there for a reason, preventing the interpreter itself from crashing, which is what happens when it "exits without saying anything". Write an iteratve solution. `dir` is a builtin function, best not to overwrite it. `lenght` -> `length`. — ggorlen, Oct 04 '22 at 15:53
Thanks for your comment, i'll change dir's name. Regarding recursion i have to use it, we are told to specificly use the recursive backtracking algorithm for the generation so unfortunatly i can't switch to an iterative version of it :(. But i just don't get why im not able to generate big sizes, is it because my implementation of the algorithm was wrong ? Or is it as it should be and i can't change what's hapening — Ulquileon, Oct 04 '22 at 17:21
The safe default stack size for CPython is about 1000, so if you have a 100 x 100 grid, that's 1000 and you can expect to overflow the stack. If you increase the recursion limit, it only _might_ kick the can down the road a little bit, if you're lucky. I only glanced at the algorithm, but if it works fine on small grids with cycles then it's probably correct. If your professor expects recursion _and_ huge grids _and_ CPython, then those 3 things aren't really compatible as far as I can tell. — ggorlen, Oct 04 '22 at 17:23
Thanks for your input, i was used to programing in C and not in python that's why i was so surprised to be so "limited" but yeah i guess i can't get passed that limit without playing with fire. Although im glad to finally have the answer to the problem it was so frustrating to not know what was the issue here ! — Ulquileon, Oct 05 '22 at 08:57

DarrylG · Accepted Answer · 2022-10-05T15:09:57.390

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)

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

1 Answers1