Here's the simple code:
plaintext function fib(n) if n ≤ 1 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(2n).
Space complexity: O(n) exponential due to repeated subproblems, stack depth is n.