Exponential Example

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 $2^n$ nodes.

fib($30$) makes over $1$ million calls. fib($40$) makes over $300$ million. The tree grows exponentially.

Memoization reduces this to $O(n)$ time and $O(n)$ space by caching results. Without it, exponential blowup kills performance.