What is the maximum recursion depth in Python, and how to increase it?


Question

I have this tail recursive function here:

def fib(n, sum):
    if n < 1:
        return sum
    else:
        return fib(n-1, sum+n)

c = 998
print(fib(c, 0))

It works up to n=997, then it just breaks and spits a "maximum recursion depth exceeded in comparison" RuntimeError. Is this just a stack overflow? Is there a way to get around it?

1
314
1/28/2017 11:41:36 PM

Accepted Answer

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn't optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimit and change the recursion limit with sys.setrecursionlimit, but doing so is dangerous -- the standard limit is a little conservative, but Python stackframes can be quite big.

Python isn't a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

359
8/2/2019 10:45:43 AM

Looks like you just need to set a higher recursion depth

sys.setrecursionlimit(1500)

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon