Memoization
Top-down recursion that caches each result. The recursion tree collapses to one expansion per state.
Recursion Trees: fib(6) with memoization
fib(2) is in the cache already, 1. It returns at once: no subtree is built here.
Cost
- Space
- O(states)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Recursion Trees covers these too, in the same run.