TwiddleLab / Code / Recursion: Functions That Call Themselves
Remember Answers: Memoization
What you will learn
- Memoization: keep a notebook of answers. Before working something out, look it up; after, write it down.
- In Python the notebook is a dictionary: key n, value fib(n).
- With it, fib(n) makes 2n - 1 calls instead of millions: each value is worked out once.
- The same idea counts paths in a grid: each cell is worked out once from its neighbours.
How the lesson goes
Your app asks the same hard question 1,000 times. Should it solve it 1,000 times?
fib(15) made 1973 calls. Now it gets a notebook: once fib(k) is known, it's written down. Guess the calls now.
Be the notebook for fib(6).
Each new call: tap the circle to work it out, or tap its notebook page if the answer is already there.
Without a notebook fib(6) works out fib(4) twice, fib(3) three times and fib(2) five times. With it, the second time any of them is asked, the answer is read in one step.
fib(15) with and without the notebook.
Same function, same answer. Count the calls.
Memoization.
Memoization means remembering answers. Keep a notebook; it's a dictionary, memo = {}.
Before working out fib(n), check: if n in memo, return memo[n]. After working it out, write it: memo[n] = the answer.
Each answer is computed once. The call tree shrinks from a bushy tree to a single chain.
Give fib a notebook.
Check the notebook first, then the base case, then work it out and write it down. Make fib(30) print 832040.
The look-up must come before any work, or it saves nothing. Writing memo[n] before returning it is what fills the notebook for later calls.
What's in the notebook after fib(6)?
Fill each page. Each value is the sum of the two pages before it.
fib(2) = 1 + 0 = 1, fib(3) = 1 + 1 = 2, fib(4) = 2 + 1 = 3, fib(5) = 3 + 2 = 5, fib(6) = 5 + 3 = 8. Only n of 2 or more reach the line memo[n] = ...
How many paths from start to the far corner, moving only right or down?
paths(cell) = paths(cell above) + paths(cell to the left). Fill the grid, each cell once.
Point your memo fib at month 30 and month 70.
Without a notebook, fib(70) would take years. Press Run.
With the notebook, how many calls does fib(20) make?
fib(6) made 11 calls, fib(15) made 29, fib(30) made 59.
With the notebook, fib(n) calls fib(n - 1), fib(n - 2) ... down to fib(1): n calls. On the way, each level's second call is a look-up or base case: n - 1 more. Total 2n - 1.
Both trees compute fib(6). Which one used a notebook?
Tap a tree, then Check.
The bushy tree recomputes fib(4), fib(3) and fib(2). The thin tree computes each once; later requests are dashed look-ups with nothing below them.
Previous lesson: Trees of Calls · Next lesson: Towers of Hanoi · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
