Why doesn't this recursive Fibonacci function in Python give me a recursion depth error?

Question

I have the following Python (3.12) code for finding Fibonacci numbers recursively, and keeping track of how many times the function is called.

fibcalls = 0
def fib(n):
 global fibcalls
 fibcalls += 1
 if n < 2: return n
 return fib(n-1)+fib(n-2)

I can run this for fib(40). It takes a while (but gets there before I give up). If I then check the value of fibcalls, which counts how many times the function has been called, I get a value of 331160281ドル$.

My question is: Why isn't recursion depth exceeded so as to give me an error message?

A little more background: I am a math professor teaching a discrete math class to computer science majors. I would like to explain why our recursive factorial function can't even get to 1100ドル$ calls (for calculating factorial(1100ドル$)), but our recursive Fibonacci function can make over 300ドル$ million calls without an error. I do have a theory: Namely: Calls to a given value only appear on the stack once, even though they are needed many times in the recursion. But that's just a guess.

Any further information would be welcome.

Answer 1

You're conflating the depth of the function-call tree with the size of the function-call tree.

The recursion depth = height of function-call tree = max number of stack frames on function-call stack at any time. This relates to the amount of memory needed to implement the function calls. For fib(n), it is linear in n.

The size = total # function calls. This relates to the amount of time needed to make all of the function calls. For fib(n), it is exponential in n.

Your theory is incorrect in Python. If it were true, computing fib(40) would be near instantaneous.