Asking the Same Question Twice: Memoization

Speed up a recursive function that answers 10 stairs at once, 40 in half a minute and 50 in about an hour: why a faster computer and a loop with your own stack don't help, where the time really goes, and how writing each answer down, memoization, makes it instant.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Explain memoization as remembering answers so the same question isn't worked out twice
  • Add memoization to a recursive function and say how it changes the Big-O

Key takeaways

  • Some recursion asks the same smaller question many times, and the repeats make the work grow like O(2ⁿ): each extra stair multiplies it by about 1.6.
  • A faster computer buys a stair or two, and a loop with your own stack does the same repeated work: the problem is the repeats, not the depth.
  • Memoization keeps each answer the first time it's worked out, and looks it up every time after that.
  • With the answers written down, each question is worked out once, so the staircase count drops from O(2ⁿ) to O(n), using O(n) memory for the notes.
  • Building the answers from the smallest up in a table, with no recursion, is called dynamic programming.

Before this: every recursive function so far asked each smaller question once: each folder, each doll, each section, one call each. This one doesn't, and it shows.

A puzzle app has a staircase question of the day: you climb taking 1 or 2 stairs at a time, so how many different ways are there to climb to the top? Three stairs can be climbed 3 ways: 1+1+1, 1+2 or 2+1. The app's answers come from a recursive function, and it's right every time. It's also slow in a way that's hard to believe. In Python it answers 30 stairs in about a quarter of a second, 35 in about 2 seconds, 40 in about half a minute, and 50 in about an hour.

Here's how the function works. Your last move onto the top stair was either a 1-stair step, from one stair below, or a 2-stair step, from two below. So:

  • Recursive case: the ways to climb n stairs = the ways to climb n − 1, plus the ways to climb n − 2.
  • Base case: 1 stair can be climbed 1 way, and 0 stairs 1 way too (you're already there). So for 1 stair or fewer, the answer is 1.

Here it is, with a counter of how many calls each answer took:

int calls = 0;

long Ways(int stairs)
{
    calls++;
    if (stairs <= 1)
    {
        return 1;
    }
    return Ways(stairs - 1) + Ways(stairs - 2);
}

foreach (int stairs in new int[] { 10, 20, 25 })
{
    calls = 0;
    long ways = Ways(stairs);
    Console.WriteLine("Stairs: " + stairs + ", ways: " + ways + ", calls: " + calls);
}
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
int calls = 0;

long ways(int stairs) {
    calls++;
    if (stairs <= 1) {
        return 1;
    }
    return ways(stairs - 1) + ways(stairs - 2);
}

void main() {
    for (int stairs : new int[] {10, 20, 25}) {
        calls = 0;
        long answer = ways(stairs);
        IO.println("Stairs: " + stairs + ", ways: " + answer + ", calls: " + calls);
    }
}
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
calls = 0


def ways(stairs):
    global calls
    calls += 1
    if stairs <= 1:
        return 1
    return ways(stairs - 1) + ways(stairs - 2)


for stairs in [10, 20, 25]:
    calls = 0
    answer = ways(stairs)
    print(f"Stairs: {stairs}, ways: {answer}, calls: {calls}")
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
let calls = 0;

function ways(stairs) {
  calls++;
  if (stairs <= 1) {
    return 1;
  }
  return ways(stairs - 1) + ways(stairs - 2);
}

for (const stairs of [10, 20, 25]) {
  calls = 0;
  const answer = ways(stairs);
  console.log(`Stairs: ${stairs}, ways: ${answer}, calls: ${calls}`);
}
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
let calls = 0;

function ways(stairs: number): number {
  calls++;
  if (stairs <= 1) {
    return 1;
  }
  return ways(stairs - 1) + ways(stairs - 2);
}

for (const stairs of [10, 20, 25]) {
  calls = 0;
  const answer = ways(stairs);
  console.log(`Stairs: ${stairs}, ways: ${answer}, calls: ${calls}`);
}
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785

The answers are right, but look at the calls: 177, then 21,891, then 242,785. Five more stairs make it about ten times the work, and each single stair about 1.6 times. That's the doubling growth from Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ): roughly O(2ⁿ), read "big O of two to the n". 30 stairs takes 2.7 million calls, and 50 stairs about 40 billion.

What would you try?

A faster computer. Twice the speed sounds like a lot. But every extra stair multiplies the work by about 1.6, so twice the speed buys about a stair and a half. The 50-stair puzzle goes from about an hour to about half an hour.

A loop with a stack of your own, the fix from 5,000 Folders Deep: Recursion or a Loop? That fixed depth, and this staircase is only 50 calls deep. Put the questions on a pile instead of the call stack, and you still answer 40 billion of them. The pile doesn't make the work smaller.

Cap the puzzle at 30 stairs. It's fast again, and it's the feature removed, not fixed.

What we tried 50 stairs Where it breaks
Plain recursion about 40 billion calls, about an hour in Python each stair multiplies the work by 1.6
A computer twice as fast about half an hour it buys a stair and a half
A loop with your own stack still about 40 billion steps the depth was never the problem
A cap at 30 stairs fast the puzzle can't ask for 50

The questions that lead to it

Where do all those calls come from? Draw the calls for 5 stairs as a tree. Ways(5) asks Ways(4) and Ways(3). But Ways(4) asks Ways(3) too, so the whole Ways(3) question is worked out twice, and Ways(2) three times. Each call starts from scratch, because nothing remembers an answer.

The calls for 5 stairs drawn as a tree of 15 boxes: Ways(5) at the top, branching to Ways(4) and Ways(3), and so on down to Ways(1) and Ways(0). Both Ways(3) boxes are yellow and all three Ways(2) boxes orange, marked "asked again": the same questions, worked out from scratch each time

How many different questions are there, really? For 5 stairs, only six: Ways(0) to Ways(5). The 15 calls are those six questions asked over and over. For 50 stairs, 51 different questions are asked about 40 billion times.

What would you do if a friend asked you the same sum twice? Say they ask what 17 × 23 is. You work it out on paper, 391, and tell them. An hour later they ask again. You don't multiply again: you look at the paper. So what if the function did the same: worked each stair count out once, wrote the answer down, and read it back every time after?

How it got its name

This idea was so useful that it got a name: memoization (read "mem-oh-ih-ZAY-shun"), from memo, a note to yourself. It's not a typo for "memorization", though the idea is close. Keep a list of answers, one slot per stair count, all empty to start. Before working anything out, look in the slot: if the answer's there, return it. If not, work it out, and write it in the slot before you return it.

A desk with a stack of yellow sticky notes, each with a stair count and its answer written on it, next to a worked-out sum on scrap paper crossed out: once an answer is written down, it's read from the note instead of worked out again

Write the answer down

int calls = 0;
long[] known = new long[51];

long Ways(int stairs)
{
    calls++;
    if (stairs <= 1)
    {
        return 1;
    }
    if (known[stairs] != 0)
    {
        return known[stairs];
    }
    long answer = Ways(stairs - 1) + Ways(stairs - 2);
    known[stairs] = answer;
    return answer;
}

foreach (int stairs in new int[] { 10, 20, 25, 50 })
{
    calls = 0;
    Array.Clear(known);
    long ways = Ways(stairs);
    Console.WriteLine("Stairs: " + stairs + ", ways: " + ways + ", calls: " + calls);
}
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
int calls = 0;
long[] known = new long[51];

long ways(int stairs) {
    calls++;
    if (stairs <= 1) {
        return 1;
    }
    if (known[stairs] != 0) {
        return known[stairs];
    }
    long answer = ways(stairs - 1) + ways(stairs - 2);
    known[stairs] = answer;
    return answer;
}

void main() {
    for (int stairs : new int[] {10, 20, 25, 50}) {
        calls = 0;
        Arrays.fill(known, 0);
        long answer = ways(stairs);
        IO.println("Stairs: " + stairs + ", ways: " + answer + ", calls: " + calls);
    }
}
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
calls = 0
known = [0] * 51


def ways(stairs):
    global calls
    calls += 1
    if stairs <= 1:
        return 1
    if known[stairs] != 0:
        return known[stairs]
    answer = ways(stairs - 1) + ways(stairs - 2)
    known[stairs] = answer
    return answer


for stairs in [10, 20, 25, 50]:
    calls = 0
    known = [0] * 51
    answer = ways(stairs)
    print(f"Stairs: {stairs}, ways: {answer}, calls: {calls}")
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
let calls = 0;
let known = new Array(51).fill(0);

function ways(stairs) {
  calls++;
  if (stairs <= 1) {
    return 1;
  }
  if (known[stairs] !== 0) {
    return known[stairs];
  }
  const answer = ways(stairs - 1) + ways(stairs - 2);
  known[stairs] = answer;
  return answer;
}

for (const stairs of [10, 20, 25, 50]) {
  calls = 0;
  known = new Array(51).fill(0);
  const answer = ways(stairs);
  console.log(`Stairs: ${stairs}, ways: ${answer}, calls: ${calls}`);
}
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
let calls = 0;
let known: number[] = new Array(51).fill(0);

function ways(stairs: number): number {
  calls++;
  if (stairs <= 1) {
    return 1;
  }
  if (known[stairs] !== 0) {
    return known[stairs];
  }
  const answer = ways(stairs - 1) + ways(stairs - 2);
  known[stairs] = answer;
  return answer;
}

for (const stairs of [10, 20, 25, 50]) {
  calls = 0;
  known = new Array(51).fill(0);
  const answer = ways(stairs);
  console.log(`Stairs: ${stairs}, ways: ${answer}, calls: ${calls}`);
}
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99

For 5 stairs, the second Ways(3) and the second Ways(2) now find their answers already written down, so the calls under them never happen: 9 calls instead of 15. A 0 in a slot means "not worked out yet", which is safe here because no staircase has 0 ways. The answer for 50 stairs is over 20 billion, too big for an int, so C# and Java use long; Python's whole numbers never run out of room, and JavaScript's numbers hold it exactly.

What it changes

Plain recursion With memoization
Calls for n stairs about 2 × (the answer), roughly O(2ⁿ) 2n − 1, O(n)
Memory O(n) frames on the call stack O(n) frames, plus O(n) slots for the notes
50 stairs about 40 billion calls 99 calls

Each stair count is now worked out once; every other time it's a lookup. That's the trade from Answer It in One Step: Trading Memory for Time: a little memory for the notes buys an enormous amount of time.

When notes don't help. Memoization helps only when the same questions come back. The countdown, the dolls and the folder tool ask each question once (every folder is added up once), so notes would only cost memory. Look for a recursive case that calls the function more than once, on pieces that overlap. And when only one answer is ever needed, a plain loop that keeps the last two answers, the next section's idea, does the same job without keeping 50 notes.

A first look at dynamic programming

There's another way to use the notes: skip the recursion and fill them in from the bottom up. Write the answers for 0 and 1 stairs (1 and 1), then each next slot is the sum of the two before it: 2, 3, 5, 8, 13… up to the slot you need, with one loop. Building answers from the smallest up in a table like this is called dynamic programming. Memoization works from the top down and dynamic programming from the bottom up, and both rest on the same idea: never work out the same answer twice.

Try it. Add 40 to the list of stair counts in the plain version and run it, then in the memoized version. The plain one makes over 300 million calls and keeps you waiting (about half a minute in Python); the memoized one makes 79 and finishes at once.

Check yourself

2 questions to try on the lesson page.

So what

When a recursive function slows to a crawl, don't reach for a faster computer: check whether it asks the same smaller question again and again. If it does, writing each answer down the first time can turn an impossible O(2ⁿ) into an easy O(n). You'll meet the same idea in real apps as a cache: a cart that doesn't recalculate the same shipping price, a page that keeps the weather it fetched a minute ago.

Key terms

Cheat sheets