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 , it finishes in milliseconds. But try 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: .
Space complexity: exponential due to repeated subproblems, stack depth is n.