# 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 November 17, 2026

By Gregor Dzierzon

## 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:

```csharp
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);
}
```

```text
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
```

```java
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);
    }
}
```

```text
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
```

```python
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}")
```

```text
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
```

```javascript
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}`);
}
```

```text
Stairs: 10, ways: 89, calls: 177
Stairs: 20, ways: 10946, calls: 21891
Stairs: 25, ways: 121393, calls: 242785
```

```typescript
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}`);
}
```

```text
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](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/eb80b1f088fa4fb58c494ab1862289bc.webp)

**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](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/b1f6420060df488f8c4a28623bad58bb.webp)

## Write the answer down

```csharp
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);
}
```

```text
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
```

```java
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);
    }
}
```

```text
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
```

```python
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}")
```

```text
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
```

```javascript
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}`);
}
```

```text
Stairs: 10, ways: 89, calls: 19
Stairs: 20, ways: 10946, calls: 39
Stairs: 25, ways: 121393, calls: 49
Stairs: 50, ways: 20365011074, calls: 99
```

```typescript
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}`);
}
```

```text
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

- [Memoization](https://www.ask-codey.com/glossary/memoization-data-structures)
- [Dynamic Programming](https://www.ask-codey.com/glossary/dynamic-programming)
- [Exponential Time](https://www.ask-codey.com/glossary/exponential-time)

## Cheat sheets

- [Asking the Same Question Twice: Memoization](https://www.ask-codey.com/cheat-sheets/ds-memoization-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-memoization
