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

Question

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

Did you ever consider that the recursion limit is set precisely to avoid these crashes? — juanpa.arrivillaga, May 29 '18 at 21:32
Could you provide a pretty-printed example of your maze for us to test with? — Noctis Skytower, May 29 '18 at 21:33
@NoctisSkytower I don't if this is considered pretty printing, but u can just copy paste it. the star is the starting point: maze = [['#']*10, ['#',' ',' ',' ',' ',' ',' ',' ',' ','#'], ['#',' ','#',' ','#',' ','#',' ',' ','#'], ['#',' ','#',' ','#','#','#',' ','#','#'], ['#',' ','#','#','#','*','#',' ',' ','#'], ['#',' ','#',' ',' ',' ','#','#',' ','#'], ['#',' ','#',' ','#','#','#','#',' ','#'], ['G',' ','#',' ',' ',' ',' ',' ',' ','#'], ['#']*10] — Mansour Zayer, May 29 '18 at 21:37
@FredLarson Actually I read that answer before posting my question. It just mentioned that increasing the limit is dangerous, I didn't see the reason. my question is that my only solution is changing my algorithm and avoiding recursions or is there any other way? — Mansour Zayer, May 29 '18 at 21:39
Basically, the layers of recursion take up space in memory. If you fill up the memory with these layers (called the stack), then your program runs out of memory and crashes. You'll need to come up with a more clever solution. — Patrick Haugh, May 29 '18 at 21:42
You've come to the right place! (You're experiencing a stack overflow). — Larry Lustig, May 29 '18 at 21:44
Why do you think that you need recursion to solve that problem? Maybe a loop is sufficient. — tangoal, May 29 '18 at 21:47
@MansourZayer Please edit that information into your question, don't paste it into a comment. More generally, read [mcve] in the help, and make sure to edit in all the information needed to answer your question. — abarnert, May 29 '18 at 21:47
@MansourZayer You can reduce memory consumption if you don't use functions and emulate program stack using a list. The problem is that it's a lot harder to program in such style (recursive code is a lot easier to reason about than iterative). But python sucks in recursion - its stack frames are large as hell — Andrii Maletskyi, May 29 '18 at 21:48
@tangoal Recursion is arguably a simpler way to think about this problem. Obviously you can simulate any recursive solution into a loop with an explicit stack, but if you can't simplify it any further than that, you're just making it harder to understand. (Of course sometimes you need to do that as an optimization, but that shouldn't be the first thing you jump to.) — abarnert, May 29 '18 at 21:48
The recursion limit is by default high enough that in most cases (including this one), you shouldn't hit it unless you have a bug in your code. This little board is not going anywhere near the usual limit if the code is correct. — Alex Hall, May 29 '18 at 21:52
One more thing is that by default stack size is quite small (about 8MB in linux). But it can be changed, using system utilities. Or even within python like this: `sys.setrecursionlimit(10**6); threading.stack_size(10**8); thread = threading.Thread(target=main); thread.start(); thread.join();` — Andrii Maletskyi, May 29 '18 at 21:55
@AlexHall I think you have a point there. I copy-pasted the code from a source and can't be 100% sure it works perfectly. although I have checked it several times and couldn't find any bugs — Mansour Zayer, May 29 '18 at 21:58
@abarnert: yes, you are right. However, it is an alternative in extreme situations. Here the increase of the stack size / recursion limit is easier of course. The alternative implementation by a loop could be interesting, too. — tangoal, May 29 '18 at 22:12
Are you saying that `if solve_maze(x, y):` is *inside* the body of `solve_maze`? That's definitely a recipe for infinite recursion. — Alex Hall, May 29 '18 at 22:25

score 1 · Answer 1 · answered May 29 '18 at 21:42

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.

I haven't done much else. I literally copy-pasted your code and run it. same thing. I use 32-bit IDLE ide on windows 10, python 3.6.5. — Mansour Zayer, May 29 '18 at 21:47
By same thing, do you mean you get the recursion limit exceeded error? Here is a demo of it working in Python 3.6.1: https://repl.it/repls/EvenNormalData Using Windows or IDLE really shouldn't matter. — Alex Hall, May 29 '18 at 21:51
please review my question. I have edited it, and now the code works — Mansour Zayer, May 29 '18 at 22:03

Mansour Zayer · Accepted Answer · 2018-05-29T22:58:23.107

The information I gathered are as follows:

the problem is due to stack overflow.
editing this limit is not advised.
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.
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.

score 0 · Answer 3 · answered May 30 '18 at 16:16

0

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.

answered May 30 '18 at 16:16

tangoal

724
1
9
28

I didn't understand the 'opposite direction' part. What do you mean? – Mansour Zayer May 30 '18 at 20:15
Example: Last Position was: x = 5, y = 8 and New Position is: x = 6, y = 8. Even if you know that the last position was x=5 and y=8, you call the solve_maze (x - 1, y) for the new position, so that you go back to the last position. – tangoal May 30 '18 at 20:21

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

3 Answers3