Recursion · Stage 3 of 3
Memoized Recursion (Top-Down)
Cache repeated subproblem results by argument key
Foundations
So far, each call's smaller calls were all different, so nothing was computed twice. Now, what if a call needs two smaller answers whose own calls overlap, so the same argument comes up again and again?
Memoization caches each call's result in a hash map keyed by its arguments. Before doing any work, a call checks the map: a hit returns the stored answer at once, and a miss computes it, stores it, and returns it. Each distinct argument is then solved once, so the cost is the number of distinct arguments times the work per call, not the size of the whole call tree.
Count the ways to cut nums = [7, 1, 5, 3, 6] into consecutive pieces of length 1 or 2. The last piece is one element or two, so cuts(i) = cuts(i - 1) + cuts(i - 2) for the first i elements, with cuts(0) = cuts(1) = 1. Uncached, cuts(5) computes cuts(3) twice and cuts(2) three times; keyed by i, each is computed once, and cuts(5) = 8.
cuts(i). Every argument is computed once and stored, so the second cuts(2) and cuts(3) are cache hits: 9 calls instead of the 15 an uncached recursion makes.Case Scenario
The problem
Fibonacci Number
Compute the nth Fibonacci number. Write the recursive definition first — base cases F(0)=0 and F(1)=1, then trust F(n-1) and F(n-2). Memo is optional here.
- Input
- n = 5
- Output
- 5
Fibonacci Number is that recurrence with different base cases: fib(0) = 0, fib(1) = 1, and fib(n) = fib(n - 1) + fib(n - 2). Written directly, fib(n - 1) recomputes everything fib(n - 2) needs, so the calls roughly double per level. Keyed by n, a memo solves each argument once. For n = 5, the answer is 5.
The direct approach translates the definition: fib(n) calls fib(n - 1) and fib(n - 2). Both branches rebuild the same smaller answers, so fib(2) is computed 3 times for n = 5, and the number of calls grows by about 1.6 for every step in n: over 2.6 million calls for fib(30).
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.