quantumSoup - 8 months ago 40

Python 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`

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 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.