The figure shows the call tree for naive <code>fib(4)</code>. Notice that
- A
Tree has constant depth
- B
No base cases
- Ccheck_circle
Subproblems repeat (e.g., fib(2) computed multiple times) — exponential
- D
Each subproblem solved once
Explanation
Repeated subproblems make naive Fibonacci exponential; memoization fixes it.