5

I have this recursive factorial function:

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n-1)

Doing factorial(998) works, but factorial(999) will raise a RecursionError: maximum recursion depth exceeded in comparison.

Why does it error at factorial(999) and not 1000 or 1001? factorial(1) hits the base case, so there should only be one stack frame from calling the factorial function, factorial(2) recurses once, so it should use 2 stack frames and so on.

Is the recursion limit exclusive or inclusive? As in, if you setrecursionlimit(1000) does it error when you reach 1000 stack frames or when you exceed 1000?

If it's exlusive, why does it error on n=999 instead of n=1000? n=999 should create 999 frames, not 1000. Where does the extra stack frame come from that makes it hit 1000? If the limit is inclusive, where do the extra 2 stack frames come from that make it hit 1001 stack frames?

Boris Verkhovskiy
  • 14,854
  • 11
  • 100
  • 103

1 Answers1

3

See for yourself. Python has great introspection tools:

import inspect

def factorial(n):
    if n < 2:
        return 1
    print(len(inspect.stack()))
    return n * factorial(n-1)

Global level is already at 1-depth. First function call is 2-depth, so there's a one 'extra' stack frame in your calculations.

def f():
    print(len(inspect.stack()))

print(len(inspect.stack())) # 1
f() # 2
RafalS
  • 5,834
  • 1
  • 20
  • 25
  • Yea, I did some experimenting and figured it out https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it?noredirect=1#comment104887028_3323001 but I was hoping someone could explain everything and give a certain answer. – Boris Verkhovskiy Dec 15 '19 at 20:06
  • 1
    Possibly even link to where this recursion limit check happens in the CPython source code. I think it's here [`(++tstate->recursion_depth > _Py_CheckRecursionLimit);`](https://github.com/python/cpython/blob/51edf8aaa2e17626f9690ed29d25945fc03016b9/Include/cpython/ceval.h#L45) but that looks like it sould error when you *exceed* 1000, not when you hit 1000 stack frames. So is `recursion_depth` always 1 higher than it should be? Does the interpreter add another frame that doesn't appear in stack traces? Or am I missing some other context? – Boris Verkhovskiy Dec 15 '19 at 20:12
  • Err, the recursion limit check happens here https://github.com/python/cpython/blob/b08d3f71beab59653edfbbcf7b92a7bc8050d6b8/Python/ceval.c#L697 `tstate->recursion_depth > recursion_limit` – Boris Verkhovskiy Dec 15 '19 at 20:20