Overlapping Subproblems
The same subproblem recurs many times in the naive recursion. That repetition is what memoization removes.
Recursion Trees: fib(5), the plain tree
fib(5) is not a base case, so it calls fib(4) first and fib(3) after that.
Cost
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Recursion Trees covers these too, in the same run.