##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Naive Fibonacci)
The recursive formula fib(n) = fib(n-1) + fib(n-2) spawns two recursive calls per level. This creates a binary tree of calls with roughly nodes.
fib() makes over million calls. fib() makes over million. The tree grows exponentially.
Memoization reduces this to time and space by caching results. Without it, exponential blowup kills performance.