AlgoScope

Memoization

Top-down recursion that caches each result. The recursion tree collapses to one expansion per state.

Dynamic programming, technique, intermediate
Cache hit for fib(2).f1=1f2=1f0=0f3=2f1=1f(4)f(2)f(5)f(6)call

Recursion Trees: fib(6) with memoization

Decision, step 15 of 24

fib(2) is in the cache already, 1. It returns at once: no subtree is built here.

How recursion trees works

Cost

Space
O(states)

Leads to

Topics that need this one first.

Taught by the same lesson

Recursion Trees covers these too, in the same run.