Memoization

Why it matters

Some recursive solutions are correct and still far too slow. They work, but they solve the same small question again and again until the computer is busy for minutes on an input of size 40. Dynamic programming, usually shortened to DP, is a family of methods that fix this. The core move is simple: solve each small question once, remember the answer, and reuse it. DP is one of the most tested topics in coding interviews, and it shows up in real software too, from spell checkers to bioinformatics to route planning. This module teaches the method from the ground up in C++, and the first lesson starts with the simplest tool in the box: memoization.

You do not need prior knowledge of DP. You need to know how to write a function in C++, how a vector works, and how to compile and run a program. If any of those feel shaky, go back to the earlier modules in the track first.

The idea

Imagine a teacher who gets the same maths question fifty times in one afternoon. The first time, the teacher works it out slowly on the board. The second time, the teacher should not redo the working. A sensible teacher writes the answer on a sticky note and reads the note the next time the question comes up.

Memoization is that sticky note for a function. You store the result of a call. When the same call comes again, you read the stored result and skip the work. The word comes from "memo", a short note, and the technique is the basis of top-down DP.

Before we write any code, let us measure the problem. Here is the most natural way to write a Fibonacci function. The Fibonacci numbers start 0, 1, and every later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, and so on. The natural recursive version reads almost like the definition.

fib(n) = n                       if n is 0 or 1
fib(n) = fib(n - 1) + fib(n - 2) otherwise

Translating that into C++ gives a function with two recursive calls. The problem is hidden in those two calls. To compute fib(5), the function calls fib(4) and fib(3). To compute fib(4), it calls fib(3) and fib(2). The value fib(3) is now computed twice, and both copies do the same work. Every level of the tree doubles the amount of repeated work. That is why the plain version becomes unusable so quickly.

The picture below shows the calls for fib(4) as a tree. Each box is one call. The two orange boxes are the same question, fib(2), and the program works it out twice.

Call tree for fib(4) with the repeated fib(2) call highlighted in orange

Two words will carry the rest of this module. A subproblem is a smaller version of the big question, such as "what is fib(3)?". A state is the set of numbers that identify one subproblem. For Fibonacci, the state is a single number, n. For a grid problem, the state might be a row number and a column number.

DP applies when a problem has two properties:

• Overlapping subproblems. The same smaller subproblems come up again and again. Plain recursion repeats the work every time. DP stores the answer and reuses it.
• Optimal substructure. The answer to the big problem can be built from answers to smaller problems. For Fibonacci, fib(n) is exactly fib(n - 1) + fib(n - 2). For many other problems, the best answer for a big input is built from the best answers for smaller inputs.

If a problem has both properties, DP usually works. If it lacks overlapping subproblems, the cache never gets used, and you gain nothing. Sorting an array, for example, has optimal substructure but no repeated subproblems, so DP is the wrong tool for it.

What happens inside a function call

To understand why repeated calls cost so much, you need a picture of what the computer does when a function calls another function. This picture is also the key to understanding memoization.

When fib(5) runs, the computer stores a small block of memory for that call. The block is called a stack frame. It holds the parameter n and the place in the code to return to. The frames sit on a region of memory called the call stack. A new call pushes a frame on top. When the call returns a value, its frame is popped off. Only the frame on top is active at any moment.

Here is what the stack looks like while fib(5) is waiting for fib(4), which is waiting for fib(3):

top of stack
  fib(3)   waiting to add its two results
  fib(4)   waiting for fib(3) and then fib(2)
  fib(5)   waiting for fib(4) and then fib(3)
bottom of stack

The frames are pushed and popped in a strict order. The function on top always finishes first. That is why the call stack is also called a last-in, first-out structure. The Viz below shows this for fib(4). Step through the animation, and watch the frames grow and shrink as the calls go down and the answers come back up.

Notice two things while you watch. First, the same call can appear more than once in the whole run, even though it appears only once on the stack at any moment. Second, the depth of the stack is the longest chain of waiting calls. For fib(n), the depth is about n, so the stack is small. Deep recursion has a cost of its own, which we come back to later.

Measuring the waste

Before you trust any speed-up, measure the work. A good habit is to add a counter that goes up each time the function runs. The counter tells you how many calls a version makes, and that number is far more honest than a stopwatch on a small input.

Here is a complete program. It runs the plain version and the memoized version for n = 30 and counts the calls. It takes no input, so just press Run.

Output:

plain fib(30) = 832040, calls = 2692537
memo  fib(30) = 832040, calls = 59

Both versions return the same answer, 832040. The plain version makes 2,692,537 calls. The memoized version makes 59. The difference is the whole point of this lesson.

Look at the memoized function line by line. The counter memoCalls goes up on every call, including the calls that return at once from the cache. The line if (n <= 1) return n; handles the two base cases. A base case is an input so small that the answer is known without recursion. Next comes the cache check. The vector memo holds one slot for each n. The value -1 means "not computed yet". Fibonacci values are never negative, so -1 can never be a real answer. If the slot holds a real value, the function returns it at once.

If the slot is empty, the function computes the answer with the two recursive calls, stores it in memo[n], and returns it. Storing before returning is the step that makes the next call cheap. Forgetting that one line is the most common bug in memoized code, and we come back to it in the mistakes section.

Why exactly 59 calls? Each value from fib(2) up to fib(30) is computed once. Each computed value makes two calls, one for each child. The count is close to two per value, so about 2n. You do not need a formal proof here. You need the habit of checking: if the counter comes out far above 2n for a memoized function, the cache is not working.

What the numbers mean for complexity

Computer scientists describe how work grows with input size using Big-O notation. Big-O ignores constant factors and focuses on the growth rate. You can read O(n) as "work grows in a straight line with n" and O(2 to the power n) as "work doubles every time n goes up by one".

The plain Fibonacci recursion makes about 1.6 to the power n calls. Computer scientists often write this as O(2 to the power n), because 2 is a simple upper bound, and both forms mean exponential time. The memoized version does about one computation per state, and each state does a constant amount of work apart from its recursive calls. So it is O(n) time. The memo table has n + 1 slots, so it uses O(n) space, plus the call stack, which is also about n deep.

Here is the same comparison in a table you can reuse for any DP problem.

The space column deserves a note. The plain version uses O(n) space too, because the deepest chain of calls is about n frames. Memoization does not make the stack smaller. It makes the work smaller. This is a common misunderstanding, and an interviewer may ask about it.

Interviewers also like to ask how big n can get. Fibonacci numbers grow fast. fib(90) is 2880067194370816120, which fits in a 64-bit signed long long. fib(92) is the largest Fibonacci number that fits. fib(93) is one step too far, so it overflows, which means the stored value wraps around to a wrong number. Overflow is not a DP problem. It is a limit of the data type. In a real problem, check the constraints before you pick a type.

The recipe for top-down DP

Memoization turns any clean recursive definition into a fast one. The steps below work for most problems you will meet at the start of this module.

1. Write the plain recursion first. Make it correct on small inputs, even if it is slow. A correct slow solution is a reference you can compare the fast one against.
2. Find the state. Ask which parameters change between calls. Those parameters are the state. In fibMemo, only n changes, so the state is n.
3. Add a memo table. Size it so every possible state has a slot. Fill each slot with a marker that means "not computed yet".
4. Check the cache first. At the start of the function, return the stored value if it is there.
5. Store before you return. Compute the answer with the recursive calls, store it in the table, and then return it.

Here is the recipe applied to a complete program. It reads n from the Input box and prints fib(n). The memo vector is sized after the input is read, because its size depends on n.

Type 50 in the Input box and press Run.

Output:

fib(50) = 12586269025

Each numbered step from the list is visible in the code. Notice that memo.assign runs after cin, so the table is the right size for whatever the learner typed. If you type 0, the table has one slot and the base case returns before the table is touched.

This style is called top-down because it starts from the big problem and recurses down toward the base cases. Its opposite, which we study in the next lesson, is bottom-up or tabulation. Top-down is usually easier to write because it copies the definition. Bottom-up is usually faster in practice and avoids deep recursion.

Worked example: a memo table with a visible state

The Fibonacci table is the simplest case, so let us look at it carefully. The next diagram shows the memo array before and after fibMemo(6) has run. Each slot is a box. The first row is the empty cache, and the second row is the cache after the call finishes.

Memo array for fib, empty before the call and filled with 0, 1, 1, 2, 3, 5, 8 after fib(6)

Read the second row from left to right. Slot 0 holds 0, slot 1 holds 1, and slot 6 holds 8. Every slot the function needed is filled, so a later call to fibMemo(6) returns immediately. The array is the whole state of the computation. That is the kind of picture to draw whenever you design a DP solution: show the state, show the stored values, and check that every value the recurrence needs is present.

Now trace a smaller run by hand, so you can see the cache do its job. Suppose memo holds -1 everywhere, and you call fibMemo(3).

1. Call fibMemo(3). n is 3, which is not 0 or 1. memo[3] is -1, so the cache misses. Make the first recursive call.
2. Call fibMemo(2). memo[2] is -1. Make its first recursive call.
3. Call fibMemo(1). It is a base case, so it returns 1. Back in fibMemo(2), now make the second call.
4. Call fibMemo(0). It is a base case, so it returns 0. fibMemo(2) stores memo[2] = 1 + 0 = 1 and returns 1.
5. Back in fibMemo(3), make the second recursive call, fibMemo(1). It is a base case and returns 1 again. No table slot is involved.
6. fibMemo(3) stores memo[3] = 1 + 1 = 2 and returns 2.

Count the calls. There are five in total: fibMemo(3), fibMemo(2), fibMemo(1), fibMemo(0), and then fibMemo(1) once more. The plain version also makes five calls for n = 3, because no value is needed twice yet. The first repeat appears at n = 4. There fib(2) is needed inside fib(3), and then again directly by fib(4). The cache answers that second request at once, and that is where the savings start.

Worked example: a grid with two changing numbers

Fibonacci has a single state. Real problems often have two or more. Imagine a robot that starts in the top-left corner of a grid and wants to reach the bottom-right corner, moving only right or down. How many different routes exist?

Think about the last move. The robot reached the target either from the cell above it or from the cell to its left. So the number of routes to a cell is the number of routes to the cell above plus the number of routes to the cell to the left. The cells on the top row and the left column each have only one route, because the robot must move straight along them. That gives a recursive definition with two parameters, the row r and the column c.

Two parameters need a two-dimensional table, or a map keyed by a pair. A map from C++'s standard library stores a value for each key and looks keys up by their order. The key here is a pair<int, int>, which holds a row and a column together. The next program uses a map so that you can see the state clearly. It reads the grid size from the Input box.

Type 3 3 in the Input box and press Run.

Output:

paths = 6
cached states = 4

Here is the trace for the 3 by 3 grid. The target is cell (2, 2). It needs cell (1, 2) and cell (2, 1). Cell (1, 2) needs (0, 2), which is on the edge and returns 1, and (1, 1). Cell (1, 1) needs (0, 1) and (1, 0), both on edges, so it returns 1 + 1 = 2. Then (1, 2) returns 1 + 2 = 3. By symmetry (2, 1) also returns 3, and (2, 2) returns 3 + 3 = 6. The four cached states are (1, 1), (1, 2), (2, 1) and (2, 2). The edge cells never enter the map, because they return before the cache step. That is a useful design choice: do not store trivial answers if the check costs more than the work.

Try 10 10 in the Input box. You should see paths = 48620, which is the number of ways to choose 9 right moves among 18 moves in total. The cache holds 81 states, one for each interior cell. Without the cache, the same program would revisit the same interior cells an enormous number of times.

The map is clear, but it is slower than an array because each lookup costs a little more work. For a fixed grid, a two-dimensional vector is the usual choice. We use it in the next lesson. The map is a good first tool because it shows the state directly.

Worked example: a scoring problem

The Fibonacci recurrence is a special case of a general pattern. Here is an everyday story with a slightly different recurrence. A team scores points by making plays worth 1, 2 or 3 points each. You want to know how many different sequences of plays add up to exactly n points. The order matters: a 1 then a 2 is a different sequence from a 2 then a 1.

The last play was worth 1, 2 or 3 points. So the number of sequences that reach n is the sum of the sequences that reach n - 1, n - 2 and n - 3. For n = 0 there is exactly one way, the empty sequence. Negative totals are impossible, so they count as zero.

Type 4 in the Input box and press Run.

Output:

ways to score 4 = 7

Check it by listing them. The sequences that add to 4 are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, and 3+1. That is seven. The values for totals 0 to 4 are 1, 1, 2, 4 and 7. Change the input to 10 and you get 274. Notice that n can be zero, and that the function handles negative numbers before it touches the table. If the order of those checks were reversed, memo[-1] would be read, which is outside the vector and undefined.

This is the first place where the base cases matter more than the recurrence. Three base cases are needed here, because the recurrence reaches back three steps. A common bug is writing only n == 0 and forgetting that n - 1 can go negative.

Recursion depth and stack limits

The memoized version is fast, but it still recurses. Each new level of recursion pushes a frame on the call stack. The stack has a fixed size. On a typical Linux or Windows setup, it is a few megabytes. A small function uses tens or hundreds of bytes per frame, so a depth of about 10,000 is usually safe, and a depth of 100,000 might be safe or might fail depending on the function. A depth of a million almost certainly fails.

When the stack runs out, a program usually stops with an error. On Linux the shell prints a message like this:

Segmentation fault (core dumped)

That message is the operating system's way of saying the program touched memory it was not allowed to use. It often comes from a stack that grew too deep. Memoization does not change the depth, because each new state still needs its own frame on the way down. Bottom-up DP, which we study next, has no recursion at all, so it avoids this problem entirely.

For the module's problems, the depths are small enough that recursion is fine. But when a problem's state is large, such as a grid with a million cells, switching to a loop is the correct response. Knowing when to make that switch is part of the skill.

Checking a memoized solution before you trust it

A memoized function can look right and still be wrong, so run through a short list before you move on. Each check takes less than a minute.

First, compare the memoized answer with the plain recursion on small inputs. For every n from 0 to about 15, the two must agree. The plain version is slow, but it is simple enough to be correct, so it is a reference you can trust.

Second, count the calls. For Fibonacci, a memoized call to fib(n) makes about 2n calls in total. If your count is far larger, the cache is missing somewhere, and the program is doing repeated work.

Third, test the base cases on their own. Call the function with 0, then 1, then a negative number if the input allows one. Each should return the value you wrote down by hand before you wrote the code.

Fourth, check the table size against the largest input. The table needs a slot for every value of n the program can see, so for input n the vector must hold n + 1 entries.

Fifth, reset the cache between test cases. A global table keeps its values, so a second test case may read answers that belong to the first. Call assign again at the start of each case, or pass the table in as a parameter.

If all five checks pass, the function is very likely correct. The checks also teach you what the code is doing, which is the skill that matters most when a new problem looks different from the ones you have seen.

Common mistakes

Most memoization bugs are small. Each one has a clear symptom, and learning the symptoms saves hours.

Forgetting to store the result. The function runs correctly, but it is just as slow as before. The counter tells you so: the call count still grows exponentially. The fix is the line that writes memo[n] = result before the return. In the grid example, the store comes right after the two recursive calls, not after the return.

Using 0 as the "not computed" marker. Suppose a function can legitimately return 0, and the cache uses 0 to mean "empty". Then every call with a real answer of 0 looks like a cache miss, and the function recomputes it. The result is still correct, but the speed-up is lost for those inputs. Use -1 when every real answer is non-negative, or keep a separate boolean array for "computed". The module's problems return counts and lengths, which are never negative, so -1 is a safe marker here.

A table that is too small. If you allocate memo(n) and then ask for memo[n], you write past the end of the vector. The result is undefined behaviour in C++. Sometimes it crashes, and sometimes it silently corrupts other data, which is worse. Allocate n + 1 slots when valid indexes go from 0 to n. If you want the program to stop with a clear message, use memo.at(n) instead of memo[n]. The .at() function checks the index and throws an exception. A program that calls .at(5) on a vector of five elements prints this message and stops:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

Read it from the bottom up. The what() line tells you the index and the size. The first line says the program ended because an exception was not caught. The fix is to size the table correctly, not to catch the exception.

A state that is missing a changing value. Suppose a problem asks how many ways reach a total of n using at most k coins, and your memo is keyed only by n. The first call might use all k coins and cache the answer, and a later call with a different k would wrongly reuse it. The rule is that the state must include every value that changes the answer. If a value changes between calls and affects the result, it belongs in the key.

Using a variable that is not declared. A typo such as memoo causes a compile error. Here is what g++ prints for a small program that uses memoo where it meant memo:

main.cpp: In function 'int main()':
main.cpp:7:13: error: 'memoo' was not declared in this scope; did you mean 'memo'?
    7 |     cout << memoo[2] << "\n";
      |             ^~~~~
      |             memo

The first line names the function. The next line gives the file, line 7, column 13, and the problem. g++ then shows the source line with a caret under the bad name, and it suggests the name it thinks you meant. Go to that line and look at the name. Most compile errors in DP code are typos of this kind, so read the name carefully before you change any logic.

Assuming the cache is shared across test runs. A global memo vector keeps its values for the whole program. If your program solves two test cases, the second one may read answers from the first. Clear the cache with memo.assign(size, -1) before each new case, or pass the table in as a parameter.

Debugging walkthrough

Suppose you wrote a memoized function, and it returns the wrong answer for n = 5. You want to know where the bug is. Here is a method that works for every DP bug, not only this one.

First, check the plain version. Write the recursion without any cache and run it on n = 5. Its answer is the reference. If the plain version is wrong, the bug is in the recurrence or the base cases, not in the cache.

Second, print the values as they are computed. Add a line that prints n and the result just before each return. Run the program on the small input and read the output in order. You can see the order the calls finish in, and that shows whether the cache is used when it should be.

Third, check the cache lookups. Print a message when the cache hits and another when it misses. For a correct program with n = 5, the output should show the misses for n = 2 through n = 5 appearing once each, and hits afterwards. If you see a miss for a value you already computed, the store step is missing or the key is wrong.

Fourth, check the size of the table. Print memo.size() and compare it with the largest index you use. If the program reads an index past the end, use .at() once to find out where.

This method takes a few minutes and answers most questions. The aim is to see the state of the program at each step, not to guess.

Variations and edge cases

Good DP code handles the edges of the input without special cases scattered through the middle of the logic. Before you trust a memoized function, test these inputs.

• n = 0. The base case must return the right answer for zero. For Fibonacci that is 0. For the step-counting problem, it is 1, because one way (do nothing) reaches the top.
• n = 1. The smallest non-trivial input. Make sure the cache is sized so that memo[1] exists.
• Negative inputs. Either reject them at the start or return zero. The scoring function does the second, and it does the check before touching the table.
• The largest input the problem allows. Check that the table and the answer type can hold it. A long long holds Fibonacci numbers up to fib(92), which is 7540113804746346429, and up to fib(93) the value wraps and becomes wrong. Use a larger type or a modulus if the problem asks for one.

Interview questions

Interviewers test memoization in a few typical ways. Here are four with short model answers.

"What is the time complexity of your memoized Fibonacci?" Answer: O(n) time, because each state is computed once and does constant work apart from its child calls. Add: O(n) space for the table and the call stack.

"Why does memoization help, if the call stack is still O(n)?" Answer: the stack depth stays about n, but the number of calls drops from exponential to linear. Speed comes from fewer calls, not from less stack.

"What makes a problem suitable for DP?" Answer: overlapping subproblems and optimal substructure. Name both and give one example of each.

"How would you find the number of ways, not just the value?" Answer: the same recurrence works with a counting rule. Return the number of ways rather than the best value. The memo stores counts. This is the start of the counting problems in the next lessons.

Practice

1. Easy. Add a counter to fibMemo and print the number of calls for fibMemo(10). Predict the answer first.

2. Easy. Explain in one sentence why -1 is a good marker for Fibonacci but a bad one for a function whose answers can be negative.

3. Easy. For ways(n) in the scoring example, list the base cases and say why each is needed.

4. Medium. Write a memoized function stepWays(n) that counts the ways to climb n steps taking 1 or 2 steps at a time. Use stepWays(0) = 1.

5. Medium. Change the scoring function so plays are worth 1, 2, 3 or 4 points. Predict ways(4) before you run it.

6. Medium. Write the calls made by fibMemo(4) in the order they start, as a list.

7. Medium. For the grid program, predict cached states for a 4 4 input. Then run it and check.

8. Hard. Memoize the number of ways to make an amount with coins {1, 2, 5}, where order does not matter. Explain why the state must include the index of the coin you are allowed to use, not only the amount.

9. Hard. A teacher's memo is keyed only by the current total, but the function also depends on a limit k on the number of plays. Explain why the answers can be wrong and describe the key you need.

10. Hard. Compare the plain and memoized versions for n = 40 by counting calls. Estimate how long the plain version would take if one call takes one nanosecond, and say why that estimate is a useful lesson.

What you now know

• Memoization stores the result of a function call so that later calls with the same input return at once.
• A problem needs overlapping subproblems and optimal substructure before DP helps.
• The call stack holds one frame per waiting call, and deep recursion can run out of space.
• A memo table is sized to every state, and its marker must never be a real answer.
• Every state variable that changes the answer belongs in the key.
• Count the calls with a counter to prove the cache works.
• The next lesson removes the recursion and fills the table from the bottom up.