Overlapping Subproblems
The same subproblem recurs many times in the naive recursion; that repetition is what memoization removes.
Decision · step 2 of 32Recursion Trees: fib(5), the plain tree
fib(5) is not a base case, so it calls fib(4) first and fib(3) after that.
What you will see
The recursion tree for fib(6) with identical subtrees highlighted, then collapsed.
Cost
| Space | O(1) |
|---|
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Related
Taught by the same lesson
Recursion Trees covers these too, in the same run.