How safe is recursion in Python?

Question

I'm working on an AI homework, and despite my professor's suggestions, I have no intention of writing this assignment in lisp. However, I do want to write it recursively, the better to keep it concise and simple. Here is my question:

Am I running a major risk of running out of stack space if I perform a search over a large state space? How deep does the Python stack go?

Answer 1

How deep does the Python stack go?

The default recursion limit in python is 1000 frames. You can use sys.setrecursionlimit(n) to change that at your own risk.

If you're set on using python, I would suggest using a pattern more suited to the language. If you want to use the recursive style search, and need arbitrary stack depth, you can make use of python's enhanced generators (coroutines) to create a "trampoline pattern" (there an example in PEP342)

and despite my professor's suggestions, I have no intention of writing this assignment in lisp

If the exercise is intended to be recursion-based, a tail-call optimized language, like a lisp, is probably your best bet.

Answer 2

Recursion in Python (CPython, that is) cannot go deeper than sys.getrecursionlimit(). You can set this limit to a different value with sys.setrecursionlimit.

I see three options:

1. Use Lisp after all, it's optimized for recursive problems (and smart Lisp compilers will eliminate tail recursion)
2. Set the recursion limit in the recursive function to get unbounded recursion (at the risk of the program eating flaming death)
3. Use iteration with an explicit stack. A simple list will do. append is push, pop is pop.

Answer 3

>>> i=0
>>> def a():
...     global i
...     i += 1
...     try:
...             a()
...     except:
...             print(i)
... 
>>> a()
999
>>> import sys
>>> sys.getrecursionlimit()
1000

Not sure if that helps

Answer 4

Python limits the depth of recursion to a value you can find out by calling sys.getrecursionlimit and change by calling sys.setrecursionlimit. The default value isn't terribly big. If you set it too high, then you can end up blowing out the C stack when Python recurses. How high "too high" is is platform-dependent, though the default value should be safe (you get a Python exception rather than a crash) on all platforms.

There are languages that make strong guarantees about tail-call optimization. Scheme is the best-known example; it is a Lisp dialect. You should consider learning at least one Lisp-like language no matter how much you may dislike your professor.

Answer 5

As others have pointed out, you can increase the recursion depth using sys.setrecursiondepth(), though at the risk of overflowing the C stack (assuming you are using CPython). If you run into this problem, you can create a thread with bigger stack size by calling thread.stack_size() with the new stack size, and then spawn a new thread to do the actual work.