Naive Fibonacci and the explosion of the call tree

The Fibonacci sequence is defined simply: fib(0)=0, fib(1)=1, and for n≥2, fib(n)=fib(n-1)+fib(n-2). The direct translation into a recursive function seems natural:

def fib_naif(n):
    if n <= 1:
        return n
    return fib_naif(n - 1) + fib_naif(n - 2)

This code is correct, but catastrophically slow. Why? Because to compute fib(n), the function calls fib(n-1) AND fib(n-2), which themselves call back sub-parts already computed elsewhere in the tree. Look at the complete call tree of fib(5):

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
  fib(3)                (recomputes this entire subtree, already done higher up!)
    fib(2)
      fib(1)
      fib(0)
    fib(1)

For this small example with n=5, this already represents 15 function calls, even though there are only 6 distinct values (fib(0) to fib(5)) to compute. The node fib(3) is entirely recomputed twice, fib(2) three times, fib(1) five times: at each level, the number of redundant calls increases.

In reality, the total number of calls of fib_naif(n) grows exponentially with n (close to 1.618^n, the golden ratio). For n=40, this represents hundreds of millions of calls: the program becomes unusable in practice, whereas the calculation "by hand" only requires 40 additions if done cleverly.

The problem is therefore not the mathematical formula, which is correct, but the way it is computed: the same work is redone endlessly because no trace is kept of results already obtained.