Recursion and memoization

Name each subproblem by everything it reads, compute it once, and count the calls you leave waiting.

Before you read: predict

ExamHall's rubric editor remembers each node's maximum score under the node's id. When the examiner opened section s2, the side panel showed its total. She then changed two criteria; each edit copies the nodes on its path, so they are new objects that keep their ids. The panel now shows the exam's total:

What is shown?

const totals = new Map();function maxScore(node) {  if (totals.has(node.id)) return totals.get(node.id);  const score = node.children    ? node.children.reduce((sum, child) => sum + maxScore(child), 0)    : node.points;  totals.set(node.id, score);  return score;}function edit(node, id, points) {  if (node.id === id) return { ...node, points };  if (!node.children) return node;  return { ...node, children: node.children.map((child) => edit(child, id, points)) };}let exam = { id: 'exam', children: [  { id: 's1', children: [{ id: 'c1', points: 3 }, { id: 'c2', points: 4 }] },  { id: 's2', children: [{ id: 'c3', points: 5 }, { id: 'c4', points: 5 }] },] };maxScore(exam.children[1]);exam = edit(exam, 'c1', 6);exam = edit(exam, 'c3', 8);const shown = maxScore(exam);export { shown };

The 30-second version

A recursive function asks itself about smaller inputs until a base case answers. When two calls ask for the same input, the repeats multiply; a memo stores each answer once, under a key built from everything the answer reads. A memo saves repeated calls; a call that misses waits down a chain to the first stored answer or base case.

Name each subproblem by everything it reads, compute it once, and count the calls you leave waiting.

How it works

Step 1 of 13

A recursive call asks the same question about a smaller input. Each call does a little work and combines what its smaller calls return.

In the kitchen

a border ends in a small tile or a large one; what is left is a shorter border she asks the same question of → a smaller copy of the question (step 1)

Analogy: A mosaic artist pricing tile borders (decorative art)

In the studio	In the code
a border ends in a small tile or a large one; what is left is a shorter border she asks the same question of	a smaller copy of the question (step 1)
an empty border is laid in exactly one way	a base case (step 2)
she chalks each length's count on the studio wall the first time she works it out	a memo (step 6)
a count chalked by length alone, read for a job whose large tile is a different size	a key that misses an input (step 8)

In real terms: recursion turns one question into smaller ones; a memo turns each repeated smaller question into a lookup, as long as the key names everything the answer depends on.

Breaks down when: the artist sees at a glance that two borders are alike, while code compares exactly the key it was given; and her notepad never runs out of lines, while the call stack does.

Contrasting case: a border she lays tile by tile from one end with no choices: one way, no smaller question, nothing to remember.

Examples, run for real

4.1 ExamHall EXH-4950: one bank question totalled once per section

ExamHall's rubric editor totals a paper on every keystroke. A paper reused one question from the question bank in all three of its sections, so the same question object, with its three criteria, sat under three parents (EXH-4950):

4.1 EXH-4950 no memo: 25 node totals for 17 distinct nodes · the bank question and each of its criteria totalled 3 times · paper maximum 45
4.1 MR !5250 WeakMap keyed by node: 17 node totals, each distinct node once · paper maximum 45

With no memo, the bank question was totalled once per section that holds it (steps 4, 5). MR !5250 keeps each total in a WeakMap keyed by the node object: every distinct node is totalled once and the paper's maximum is unchanged (steps 6, 7). Edits copy the path to the edited criterion, so the copied nodes are new keys (step 10).

4.2 Chat: a long paste, recursion against a loop

A chat app counts the ways to send a pasted log in batches of one or two lines, modulo 1,000,000,007, once with a memoized recursive function and once bottom-up:

4.2 5,000 lines · memoized recursion: deepest chain of calls still computing 4,999 · bottom-up loop: no recursive call · both count 419,609,281
4.2 100,000 lines · memoized recursion: RangeError: Maximum call stack size exceeded · bottom-up loop: 967,618,232

The memo stops the repeats, but a first call still waits down one frame per line (step 11), so at 100,000 lines the stack runs out. The loop fills the counts from zero lines upward and keeps no call waiting (step 12).

Try it

Answer first, then check. Nothing is saved.

Question 1 of 8

A video player counts the ways to fill n seconds of an ad break with clips of 1, 2 or 3 seconds, played in order. It keeps only the last three counts, and its loop is complete apart from four lines:

In what order do the four lines run inside the loop, top first?

export function fills(n) {  let a = 1;  let b = 1;  let c = 2;  if (n < 2) return 1;  for (let i = 3; i <= n; i++) {    /* the four lines, in order */  }  return c;}

Your order

1empty
2empty
3empty
4empty

Tap the lines in the order you expect.

Question 2 of 8

A box office counts the ways to fill a row of n seats with blocks of 2 or 3 seats sold in order, such as 2 + 3 and 3 + 2 for five seats. The function is complete apart from its base case:

The team's list has 6 tests: an empty row, one seat, two and three seats, five seats, every row from 0 to 20 seats against a count kept forward in a table, and every row from 0 to 25 seats returning a number.

Which base case passes all 6?

export function blocks(n) {  /* the base case */  return blocks(n - 2) + blocks(n - 3);}

Question 3 of 8

A chat app counts the ways to fill a row of n sticker slots with stickers one or two slots wide, with no memo, and tallies every call by its input:

What is asked, the number of times tiles(3) was called?

const calls = new Array(9).fill(0);function tiles(n) {  calls[n]++;  return n < 2 ? 1 : tiles(n - 1) + tiles(n - 2);}tiles(8);export const asked = calls[3];

Question 4 of 8

A payments ledger counts the ways to repay a loan of n months in instalments covering one or two months. It keeps a memo outside the function, warms it with four calls, and records the longest chain of calls still computing:

What is deepest at the end?

const memo = new Map();let depth = 0;let deepest = 0;function plans(n) {  if (n < 2) return 1;  if (memo.has(n)) return memo.get(n);  depth++;  deepest = Math.max(deepest, depth);  const count = (plans(n - 1) + plans(n - 2)) % 1_000_000_007;  depth--;  memo.set(n, count);  return count;}for (const months of [400, 900, 1400, 1900]) plans(months);export { deepest };

Question 5 of 8

the interviewer says: "ExamHall's practice mode lets a candidate work through n questions in batches whose sizes come from a list, such as [1, 2]. Write countWays(n, steps), the number of ordered ways to finish exactly n questions, modulo 1,000,000,007. steps holds distinct positive whole numbers. It must handle n up to 100,000, and each call stands alone: a call with one steps list never sees answers from another." You have 15 minutes and a plain editor.

Before you type: say your test list out loud.

Name at least six tests, each with its input and what it expects.

Your answer (optional, stays on this page)

Question 6 of 8

Now write it, in 15 minutes, from a blank file that exports countWays.

Your answer (optional, stays on this page)

Question 7 of 8

A streaming service counts the orders in which ads adverts and trailers trailers can play in one break, bottom-up in a table:

What is result?

export function orders(ads, trailers) {  const t = Array.from({ length: ads + 1 }, () => []);  for (let a = ads; a >= 0; a--) {    for (let b = trailers; b >= 0; b--) {      t[a][b] = a === 0 || b === 0 ? 1 : t[a - 1][b] + t[a][b - 1];    }  }  return t[ads][trailers];}export const result = orders(4, 6);

Question 8 of 8

A venue app counts the routes an usher can walk from the back corner of a seating block to the front corner, one row forward or one seat across at a time. It keeps a memo, and runs counts the times a count is worked out rather than read back:

What is runs at the end?

const memo = new Map();let runs = 0;function routes(rows, seats) {  if (rows === 0 || seats === 0) return 1;  const key = rows + ',' + seats;  if (memo.has(key)) return memo.get(key);  runs++;  const count = routes(rows - 1, seats) + routes(rows, seats - 1);  memo.set(key, count);  return count;}routes(4, 6);export { runs };

Go deeper

Pro tips

Build the memo key from every argument that affects the result. When: you add a memo to a function of more than one argument, or to one that reads a setting (step 8). Verify (RAN, tips.mjs): (The curriculum row's tip, [SELF].)
```
tip 1 price(row, tier) memoized on the row alone: row A adult 80, then row A child 80 (the adult's price) · on row and tier: 80, then 40
```
Say the base cases out loud before you code: zero, one, and an input no step can reach. When: before running a recursion or a table in an interview. Verify (RAN, tips.mjs):
```
tip 2 countWays on the corner cases: n = 0, steps [1, 2] → 1 · n = 1, steps [1, 2] → 1 · n = 1, steps [2] → 0
```

Source

Vendor pages change, so their claims are labelled as of 2026-10-17; every count this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.

MDN, Recursion (glossary; the curriculum row's second source), https://developer.mozilla.org/en-US/docs/Glossary/Recursion (mdn-recursion.txt). As of 2026-10-17.
- "The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion)." (steps 1, 2)
- "Recursion is limited by stack size" (steps 3, 11)
MDN, InternalError: too much recursion, https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Too_much_recursion (mdn-too-much-recursion.txt). As of 2026-10-17.
- "RangeError: Maximum call stack size exceeded (Chrome)"
- "When there are too many function calls, or a function is missing a base case, JavaScript will throw this error." (steps 2, 11)
Tech Interview Handbook, Recursion cheatsheet, https://www.techinterviewhandbook.org/algorithms/recursion/ (tih-recursion.txt). As of 2026-10-17.
- "Make sure you have enough base cases to cover all possible invocations of the recursive function" (step 2)
- "fib(3) is being called twice! If the value for fib(3) is memoized and used again, that greatly improves the efficiency of the algorithm and the time complexity becomes O(n)." (steps 4–7)
- "Recursion implicitly uses a stack." (step 3)
- Its corner cases (tip 2): "n = 0", "n = 1".
Tech Interview Handbook, Dynamic programming cheatsheet, https://www.techinterviewhandbook.org/algorithms/dynamic-programming/ (tih-dynamic-programming.txt). As of 2026-10-17.
- "Sometimes you do not need to store the whole DP table in memory, the last two values or the last two rows of the matrix will suffice." (step 13)
- Its essential questions: "Climbing Stairs", "Coin Change".

Checked against the tools and docs as of 2026-10-17.

Predict first