CODEWITHSUNDEEP
pythonpython-3.xrecursionmaze
Mansour Zayer
Mansour Zayer

Reputation: 384

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

I've been trying to solve a maze using backtracking. The code uses multiple recursions: 

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

first time I executed the program, the "recursion limit exceeded" error showed up. To remedy that, I increased the limit:

sys.setrecursionlimit(10000)

Now that I run the program, Python crashes. What is happening? how can I solve this? Maze is not very big. its dimensions are 10*9:

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

*this is added later: at the end of solve_maze definition there was this piece of code:

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

I noticed by removing it, the program works fine.Still have no clue why

Upvotes: 2

Views: 1429

Answers (3)

tangoal
tangoal

Reputation: 769

The recursion depth is deeper than needed to solve the maze problem.

The maximum recursion depth must not be much deeper than the "length of your path up to the exit". The length of your path is 33 (= steps to be done in the 10 * 9 tiles map before the exit is reached).

If the maze would have much more branches, then also the recursion depth would grow. However, it does not sound plausible that the recursion depth exceeds several 1000s.

This has one reason: you allow to continue the search into opposite direction (so where the search comes from). This is not necessary to find the shortest path and it would massively decrease your recursion depth, if you avoid it.

Upvotes: 0

Mansour Zayer
Mansour Zayer

Reputation: 384

The information I gathered are as follows:

  1. the problem is due to stack overflow.
  2. editing this limit is not advised.
  3. the default recursion depth limit is fairly large and if the program keeps exceeding the limit, it is a sign that the code has some bug.
  4. the if solve_maze(x, y):'s statement being in the solve_maze definition body was the cause of infinite recursion.

so to sum up I found out that the problem was due to a bug causing infinite recursion and the program works fine without the need to increase recursion depth limit.

Upvotes: 0

Alex Hall
Alex Hall

Reputation: 36033

Filling in the missing parts of your code, it seems to work:

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)

The only thing I changed in solve_maze was changing maze[x][y] == ' ' to maze[x][y] in ' *' so that the starting position doesn't break it.

Output:

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

If you want to know what was wrong with your code, you need to provide a MCVE.

Upvotes: 1

Related Questions