Python max recursion, question about sys.setrecursionlimit()

Question

I have one question about sys.setrecursionlimit()

From the python docs this function:
Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care because a too-high limit can lead to a crash.

Here is my question:

Let's take this useless recursive function:

def rec(N):
     if N==0:
         return 1
     else:
         return rec(N-1);

Now let's set the max recursion to 100:

sys.setrecursionlimit(100)

If I try rec(99) (100 recursive calls), I get:

RuntimeError: maximum recursion depth exceeded

To calculate rec(99) I need to set recursion limit to 105.

Why is this so?

Solution 1

It's poorly named. It should say Stack Depth, not Recursion depth. Recursion implies it's the same thread over and over again that it's limiting. In reality, you could have actual code that just has calls 100 deep. I wouldn't recommend it, but you could. They can get away with it because in the practical world, the only times you ever run into this scenario is with recursion. When you crash because of this, seeing the word "Recursion" gives you an immediate clue of what to look for as opposed to "Stack".

(Stack should give any decent programmer the same clue, but let's be honest, your code just crashed and you want a relevant error message, right? 99.99999% of the time this tells you exactly what you messed up (you missed your base case for recursion.))

Solution 2

There are still function calls that Python runtime needs to make to even get to your function.

Solution 3

It is based on the TOTAL stack depth and not really the depth of any particular single function. You are probably already at a stack depth of 5 when you make the first call to rec().

Take for example 5 recursive functions. Each makes 98 recursive calls with the last one being to the next recursive function. With a recursion limit of 100 do you really want to allow each recursive function to make 99 calls for a total depth of ~500 calls? No, that might crash the interpreter at those depths.

Therefore the recursion limit is the maximum depth of all functions globally, not any single named function.

Comments

[Ricky Bobby]

Thx, I guess I should have read more carefully the definition and not look at the name of the function