LeetCode 509 Fibonacci - Naive Implementation

Here's the simple code:

function fib(n)
    if n ≤ 1 then
        return n
    return fib(n - 1) + fib(n - 2)

It's clean, readable, and correct. For small inputs like $fib(5)$, it finishes in milliseconds. But try $fib(40)$ and watch your CPU fan spin up. The problem isn't the code itself. It's the explosion of duplicate work happening behind the scenes. Let me show you exactly what's going wrong in the call tree.

Time complexity: $O(2^n)$.

Space complexity: $O(n)$ linear. The call stack goes $n$ frames deep before hitting the base case.