AlgoScope

Overlapping Subproblems

The same subproblem recurs many times in the naive recursion. That repetition is what memoization removes.

Dynamic programming, analysis, intermediate
Call fib(5), which expands into two calls.f(5)call
Call fib(5), which expands into two calls.f(5)call

Recursion Trees: fib(5), the plain tree

Decision, step 2 of 32

fib(5) is not a base case, so it calls fib(4) first and fib(3) after that.

Cost

Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Recursion Trees covers these too, in the same run.