Memoised recursion

Why this matters

The last lesson showed that naive Fibonacci makes about 30 million calls to compute fib(35), a number near 9 million. Most of those calls repeat work that was already done. fib(2) appears in the tree many times, and every copy computes the same answer from scratch.

This lesson removes the repeats. The change is small: keep a record of each answer, and check that record before doing any work. The technique is called memoisation, from the word "memo", a short note to remember something. A recursive function that uses a memo is called memoised recursion. It is the first dynamic programming solution most programmers write, and the later dynamic programming lessons in this course build on it.

This lesson assumes you can draw a call tree and count its calls, as taught in the recursion trees lesson.

Write the answer down

The problem, in plain words: You ask a function for the answer to a question. The function asks smaller questions, and each of those asks even smaller ones. Some smaller questions come up more than once. Without a memo, the function answers each copy again. With a memo, it answers the first copy, writes the answer down, and copies the written answer for every later copy.

A useful picture is a teacher with a notebook. A student asks, "What is fib(5)?" The teacher works it out, then writes "fib(5) = 5" in the notebook. Later, a second student asks the same question. The teacher looks in the notebook, finds the answer, and says it at once. The teacher does not work it out again.

In C++, the notebook can be a std::map. A std::map stores pairs of a key and a value. The key is what you look up, and the value is the answer stored under it. Here the key is the input n, and the value is fib(n). A map keeps its keys in sorted order and lets you find any key quickly.

A memoised function follows three steps.

1. If the input is a base case, return the answer directly, as before.
2. Look up the input in the map. If it is there, return the stored answer.
3. Otherwise compute the answer with the normal recursive rule, store it in the map, and return it.

Step 2 is the new part. Steps 1 and 3 are the same as the naive function.

Worked example 1: Fibonacci with a map

The first example uses the same Fibonacci rules as the last lesson. The map memo is declared outside the function, so every call sees the same notebook. The counter calls counts how many times the function is entered.

The output is:

n = 5  fib = 5  calls = 9  memo entries = 4
n = 10  fib = 55  calls = 19  memo entries = 9
n = 20  fib = 6765  calls = 39  memo entries = 19
n = 35  fib = 9227465  calls = 69  memo entries = 34
n = 90  fib = 2880067194370816120  calls = 179  memo entries = 89

Read the lines one at a time. The function main clears the memo before each run, so each row starts with an empty notebook. For n = 35 the function makes 69 calls instead of about 30 million, and it returns the same answer, 9227465.

The new lines are these.

memo.find(n) searches the map for the key n. It does not return the value. It returns an iterator, which is a pointer-like handle to the matching entry. If the key is not in the map, find returns memo.end(), which means "past the last entry". So the test found != memo.end() asks, "Was the key found?"

found->second reads the value stored in the entry the iterator points at. A map entry has two parts, first (the key) and second (the value). The arrow -> means "go to the part named on the right".

if (auto found = memo.find(n); found != memo.end()) is one line that declares found, runs the search, and then tests the result. The part before the semicolon declares the variable, and the part after the semicolon is the test. This form is available from C++17.

memo[n] = answer stores the answer under the key n. If the key is not in the map, it is added. If it is already there, the old value is replaced. Here it is always new, because the function only reaches this line when the key was not found.

Counting the calls

The counts in the output follow a simple rule. Each value from 2 up to n is computed once, and each computation makes two calls, one for n - 1 and one for n - 2. Those calls return at once when the value is already in the notebook, or they hit a base case. Add the root call, and you get the total.

For n = 5 the rule says there are 2 * 5 - 1 = 9 calls, which matches the output. For n = 90 the rule gives 2 * 90 - 1 = 179, which also matches. The map ends up with one entry for each value from 2 to n, so the number of entries is n - 1. For n = 90 that is 89 entries.

Compare this with the naive function from the last lesson, which made 2 * fib(n + 1) - 1 calls. For n = 35 the naive count is about 30 million, and the memo count is 69. The memo does not change the answer. It only removes the copies.

Why this is dynamic programming

Dynamic programming is a name for a family of methods. Each one breaks a problem into smaller pieces, solves each piece once, stores the answers, and reuses them. The memoised function above is that method written in the simplest way. It is sometimes called top-down dynamic programming, because it starts from the big question and works down to the small ones. The other common form fills a table from the smallest input up to the largest, and the dynamic programming module of this course covers it.

The two requirements for dynamic programming are visible in the code. The answer for each input must depend only on smaller inputs, so the recursion makes progress. And the same input must come up more than once, so storing its answer saves work. If a problem has only one path and never repeats an input, a memo saves nothing. The grid example below has repeats, and the coin example has them too.

Worked example 2: grid paths with a pair as the key

The second problem has two inputs, so the key needs two numbers. Suppose a robot stands at the top-left corner of a grid of rows and columns. It can move one square right or one square down at a time, and it must reach the bottom-right corner. How many different routes are there?

For a 1 by any grid, or any grid with one column, there is exactly one route, straight along the edge. For a bigger grid, the robot's first move is down or right, and each move leaves a smaller grid to cross. So the number of routes is the number of routes for the grid one row shorter, plus the number for the grid one column shorter.

The key is the pair (rows, cols). C++ has std::pair for this. A std::pair holds two values, and std::map can use it as a key because pairs can be sorted. The program below also includes a naive version, so you can see the difference in calls.

The output is:

naive 2x2: paths = 2, calls = 3
naive 3x3: paths = 6, calls = 11
naive 4x4: paths = 20, calls = 39
naive 8x8: paths = 3432, calls = 6863
memo  2x2: paths = 2, calls = 3, memo entries = 1
memo  3x3: paths = 6, calls = 7, memo entries = 4
memo  4x4: paths = 20, calls = 11, memo entries = 9
memo  8x8: paths = 3432, calls = 81, memo entries = 49
memo  10x10: paths = 48620, calls = 65, memo entries = 81
memo  16x16: paths = 155117520, calls = 289, memo entries = 225

The answers match between the two versions, and the call counts do not. For an 8 by 8 grid the naive version makes 6863 calls and the memo version makes 81. For a 16 by 16 grid the answer is 155117520 routes, and the memo version gets there with 289 calls. The naive version would need hundreds of millions of calls, so it is not worth running here.

Notice the memo entries. The memo is not cleared between these rows, so each count includes the entries from the earlier rows. A grid of n by n has n - 1 rows and n - 1 columns of smaller grids that can appear as keys, from 2 to n in each direction. For 16 by 16 that is 15 by 15, which is 225 entries. The memo holds one entry per distinct subproblem, and that is the whole cost of the table.

The function returns early when either side is 1, before it looks at the map. Those calls are never stored, because the answer is already known from the base case, and storing it would only use more memory.

Worked example 3: fewest coins, a harder shape

The third problem is the one most programmers meet in interviews. You have coins of values 1, 3 and 4. What is the fewest coins that add up to a given amount? For 6, the answer is 3 + 3, which is two coins. A greedy approach, which takes the biggest coin first, would give 4 + 1 + 1, which is three coins, so greedy is wrong for these coins. Recursion tries every coin at each step and keeps the best result.

The rule is: the answer for amount n is 1 plus the smallest answer among the amounts n - 1, n - 3 and n - 4. If an amount cannot be made, the function returns -1, and the memo stores that value too.

The output is:

amount 6: coins = 2, calls = 19
amount 7: coins = 2, calls = 22
amount 27: coins = 7, calls = 82
amount 100: coins = 25, calls = 301
amount 1000: coins = 250, calls = 3001

Check the first line by hand. For 6 the coins are 3 and 3, so the answer is 2. For 7 the coins are 3 and 4, so the answer is 2. For 27 the answer is six 4-coins and one 3-coin, which is 7 coins. For 1000 the answer is two hundred fifty 4-coins.

The calls follow a clean rule. Each amount from 1 up to the input is computed once. Each computed amount makes exactly three calls, one for each coin, and the top call makes three as well. So the total is 1 + 3 * amount. For 6 that is 19, for 27 it is 82, and for 1000 it is 3001. The three calls for a coin larger than the amount return -1 at once, and they are still counted, because each one enters the function.

The code has three parts that are new compared with the Fibonacci example.

The best variable holds the smallest count found so far. It starts at -1, which means "nothing found yet". The check best == -1 || rest + 1 < best handles that start value. Without the first check, the comparison with -1 would be wrong.

The static constexpr std::array holds the coin values. It is built once and never changes, so it is declared static and constexpr. The loop for (int coin : coins) visits each value in turn.

The memo can store -1 for amounts that cannot be made. The check uses find, not the stored value, so a stored -1 is still treated as a found answer. This matters, and the mistakes section shows what goes wrong with the other approach.

Common mistakes

Storing the answer but never looking it up

If the function stores answers and never checks the map before recursing, the memo does nothing. Here is the grid function with the lookup removed.

The output is:

paths = 3432, calls = 6863, memo entries = 0

The answer is right, and the call count is the naive count of 6863. The map is empty because nothing was ever stored. The fix is to add back the find check and the memo[key] = answer line.

Passing the memo by value

Each call of a function gets its own copies of its parameters. If the memo is a parameter instead of a shared variable, every call works on its own copy. The answers found by one call are lost when it returns. Here is the Fibonacci function with the memo passed by value.

The output is:

n = 10  fib = 55  calls = 177
n = 20  fib = 6765  calls = 21891
n = 25  fib = 75025  calls = 242785

These call counts are the naive counts from the recursion trees lesson. For n = 25 the formula 2 * fib(26) - 1 gives 2 * 121393 - 1 = 242785. The answer is correct, but the memo is never reused, so the function is no faster. The fix is to take the map by reference, written std::map<int, long long>& memo, so every call shares one map. Or, as in the examples above, keep the map outside the function.

Using the stored value as the test

A common shortcut is to write if (memo[n]) instead of using find. This looks right, because a stored answer is usually non-zero. But memo[n] has a side effect. If the key is missing, the bracket operator adds an entry with the value 0 and returns 0. Here is a small program that shows the side effect.

The output is:

missing key 7 reads as 0
entries after the read = 1
contains 7? 1

The read added the key 7 to the map. For this reason the examples in this lesson use find and compare the result with memo.end(). A value of 0 is also a valid answer in some problems, so testing the stored value cannot tell "missing" from "stored as 0". With other coins, such as only 2s, some amounts cannot be made and the memo stores -1 for them, which is why the test must use find.

Missing include

The map type lives in the <map> header. If you use std::map without including it, the compiler stops with an error. Here is a real error from g++ 15 for a file that includes only <iostream>.

no_include.cpp:3:6: error: ‘map’ in namespace ‘std’ does not name a template type
    3 | std::map<int, long long> memo;
      |      ^~~
no_include.cpp:2:1: note: ‘std::map’ is defined in header ‘<map>’; this is probably fixable by adding ‘#include <map>’
    1 | #include <iostream>
  +++ |+#include <map>
    2 | 
no_include.cpp: In function ‘int main()’:
no_include.cpp:6:18: error: ‘memo’ was not declared in this scope
    6 |     std::cout << memo.size() << "\n";
      |                  ^~~~

The fix is to add #include <map> at the top of the file. The second error, "memo was not declared", is a follow-on error. The compiler could not find the first declaration, so every later use of memo also fails.

Using operator[] on a const map

A const map is one the code may not change, and memo[n] may change it, because it can add a missing key. So the compiler rejects it. Here is a helper that takes the map by const reference and uses memo[n].

The first lines of the error from g++ 15 are:

const_map.cpp: In function ‘long long int lookup(const std::map<int, long long int>&, int)’:
const_map.cpp:5:18: error: passing ‘const std::map<int, long long int>’ as ‘this’ argument discards qualifiers [-fpermissive]
    5 |     return memo[n];
      |                  ^

The compiler also prints several notes about operator[] after these lines. The fix is to use find in a const function, which only reads, and to return the value if it is there. If the key is missing, return a default value, or change the parameter to a non-const reference if the function must add entries.

Using one memo for two different problems

A memo is only valid for one set of rules. The coin memo above is keyed by the amount alone, which is correct only while the coins stay 1, 3 and 4. If you change the coin list and keep the old memo, the stored answers are wrong. The safe habit is to clear the memo for each new problem, or to include the changing rule in the key.

Practice

Exercise 1. A memoised Fibonacci function is called with n = 50. Predict the number of calls, and say how many entries the memo holds.

Show the answer

The memo version makes 2 * n - 1 calls, so for n = 50 that is 2 * 50 - 1 = 99 calls. The memo holds one entry for each value from 2 to 50, which is 49 entries.

Exercise 2. The grid function in the second example is changed so the memo[key] = answer line is deleted, but the find check stays. What is the call count for an 8 by 8 grid?

Show the answer

The memo is never filled, so every lookup misses, and the function does the naive work. The count is the naive count of 6863 calls for an 8 by 8 grid, the same as the no-store program in the mistakes section.

Exercise 3. The grid memo has 225 entries after the 16 by 16 run. Explain where 225 comes from, using the rule that the function stores only grids where both sides are at least 2.

Show the answer

The stored keys are every pair (rows, cols) where rows goes from 2 to 16 and cols goes from 2 to 16. That is 15 values in each direction, so 15 * 15 = 225 keys. The early return for a side of 1 means those grids are never stored.

Exercise 4. Using the coin function, how many coins and how many calls does min_coins(6) produce? Check the calls with the rule 1 + 3 * amount.

Show the answer

The answer is 2 coins, the pair 3 + 3. The calls are 1 + 3 * 6 = 19. The program prints amount 6: coins = 2, calls = 19.

Exercise 5. The first version of the Fibonacci program did not call memo.clear() between runs. Its output showed n = 10 fib = 55 calls = 11, but the version that clears the memo shows 19 calls for the same input. Explain why the first version made fewer calls.

Show the answer

Without the clear, the memo still held the answers from the run for n = 5, which had stored values for 2 to 5. When the run for n = 10 reached 5, it found the answer in the map and returned at once, so it skipped the work for those values. The cleared memo starts empty, so it computes all values from 2 to 10 again. The two runs computed the same answer, but the first one reused old work.

Summary

• A memo is a map from an input to its answer, and a memoised function checks the map before doing any work.
• The memo version of naive Fibonacci makes 2 * n - 1 calls, down from about 2 * fib(n + 1) - 1 for the naive version.
• Each distinct subproblem is solved once, which is the core idea of dynamic programming.
• Use find and compare with end() to test for a missing key, because operator[] adds the key when it is missing.
• Clear the memo when the problem or its rules change, and pass the memo by reference when it must be shared between calls.