Advanced recursion

Recursion after the basics

The Recursion lesson covered the basics. A recursive function is a function that calls itself. It has two parts:

• The base case stops the calls.
• The recursive case calls the function again with a smaller input.

Each call that is still waiting for an answer keeps a stack frame. A stack frame is a small record of that call's variables, kept on the call stack. The call stack has a size limit. If too many calls wait at once, JavaScript throws RangeError: Maximum call stack size exceeded. This is called a stack overflow.

This lesson asks two new questions:

• What if the input is 100,000 levels deep?
• What if the data points back to itself?

Advanced recursion means choosing where the waiting work is kept. You will learn these ways:

• Keep the waiting work in an argument, so nothing waits after the call. This is a tail call.
• Return a small function for the next step, and let a loop run it. This is a trampoline.
• Keep the waiting work in your own array, and use a loop. This is an explicit stack.
• Pass a callback that says what to do with the answer. This is continuation-passing style.
• Remember the objects you have already visited, so data that points back to itself doesn't trap you.

These ideas build on earlier lessons: stack and heap, closures, WeakMap and WeakSet, and structuredClone from messaging and cloning.

A call is in tail position when it is the very last thing a function does. The function returns the call's result as it is, with no more work. A call in tail position is called a tail call.

Compare the two factorial functions below. The factorial of 5 is 5 × 4 × 3 × 2 × 1, which is 120.

1function factorial(n) {2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}5 6function factorialTail(n, acc = 1) {7  if (n <= 1) return acc;8  return factorialTail(n - 1, n * acc);9}10 11console.log(factorial(5));12console.log(factorialTail(5));

Line 3 is not a tail call. After factorial(n - 1) gives back its answer, line 3 still has to multiply it by n. So each call waits, and keeps its stack frame.

Line 8 is a tail call. factorialTail has a second parameter, acc. It is short for accumulator: a value that collects the answer as the calls go on. Line 8 multiplies first, n * acc, and passes the product to the next call. After that call, there is nothing left to do.

Lines 11 and 12 print 120 twice. Both functions give the same answer. Only the waiting work is different.

The table below explains four terms that sound alike. Read each row as: the term, what it means, and an example.

Step through factorialTail(5) below. Watch acc go from 1 to 5, then 20, then 60, then 120. The multiplication that used to wait now travels inside acc.

1function factorialTail(n, acc = 1) {2  if (n <= 1) return acc;3  return factorialTail(n - 1, n * acc);4}5 6console.log(factorialTail(5));Run

The next example throws an error in Chrome and Node on purpose. It uses strict mode and a tail call, but V8 still adds a stack frame for every call. The exact limit is different on each computer, so the example uses a large number.

1"use strict";2function dive(n) {3  if (n === 0) return "done";4  return dive(n - 1);5}6 7console.log(dive(100000));

Line 1 turns on strict mode. Line 4 calls dive again with a number one smaller. Line 7 starts at 100,000. In V8, the stack fills up long before n reaches 0. So it throws a RangeError instead of printing done.

A thunk is a function with no parameters that holds one step of work for later. For example, () => sumThunk(4, 5) is a thunk. Nothing happens until you call it.

A trampoline is a loop that keeps calling thunks until it gets back something that is not a function. In the code below, sumThunk adds the numbers from n down to 1. It doesn't call itself. It returns a thunk for the next step, and the loop calls that thunk. So the call for 4 never runs inside the call for 5. Each step starts fresh from the loop.

1function trampoline(task) {2  let current = task;3  let steps = 0;4  while (typeof current === "function") {5    current = current();6    steps = steps + 1;7  }8  return { value: current, steps };9}10 11function sumThunk(n, acc = 0) {12  if (n === 0) return acc;13  return () => sumThunk(n - 1, acc + n);14}15 16console.log(trampoline(() => sumThunk(5)).value);Run

Read the loop line by line:

1. Line 2: current starts as the first thunk.
2. Line 3: steps counts the turns of the loop.
3. Line 4: the loop goes on while current is still a function.
4. Line 5: call exactly one thunk, and keep what it gives back in current.
5. Line 6: add one to the turn count.
6. Line 8: once current is a number, return it with the count.

Line 13 is where sumThunk returns a thunk instead of calling itself. Line 16 prints 15, which is 5 + 4 + 3 + 2 + 1.

Now try a much bigger number. Pick a size below. The loop still calls one thunk per turn, so the call stack never grows.

1function trampoline(task) {2  let current = task;3  let steps = 0;4  while (typeof current === "function") {5    current = current();6    steps = steps + 1;7  }8  return { value: current, steps };9}10 11function sumThunk(n, acc = 0) {12  if (n === 0) return acc;13  return () => sumThunk(n - 1, acc + n);14}15 16const result = trampoline(() => sumThunk(100000));17console.log(result.value);18console.log(result.steps > 100000);

Often the safest rewrite is the simplest one. Keep the waiting work in an ordinary array, and loop until the array is empty. This array is called an explicit stack, because you can see it in your code.

The array lives in the heap, the big part of memory where objects and arrays are kept. The heap has far more room than the call stack. And the call stack stays one frame deep, because no function calls itself. This works well for a folder of files, a walk through a page's elements, or comment threads where users can nest replies as deep as they like.

First, here is a recursive version that counts the comments in a thread:

const comments = {
  text: "Welcome",
  replies: [
    { text: "Thanks", replies: [{ text: "You are welcome", replies: [] }] },
    { text: "Helpful", replies: [] },
  ],
};

function countComments(comment) {
  return 1 + comment.replies.reduce((total, reply) => total + countComments(reply), 0);
}

console.log(countComments(comments));

Lines 1 to 7 make a comment with two replies. The first reply has a reply of its own. Line 10 counts the current comment as 1. Then reduce goes through each reply and adds that reply's own count. So the same small function works at every level. Line 13 prints 4, for the four comments.

If users write the replies, the thread can be deeper than the call stack allows. The panel below walks a tree of files with a loop and an array instead.

1const tree = {2  name: "site",3  children: [4    { name: "index.html" },5    { name: "assets", children: [6      { name: "logo.svg" },7      { name: "app.js" },8    ] },9    { name: "notes.txt" },10  ],11};12 13function countFilesIterative(root) {14  const stack = [root];15  let files = 0;16  while (stack.length > 0) {17    const node = stack.pop();18    if (!node.children) {19      files = files + 1;20      continue;21    }22    for (const child of node.children) {23      stack.push(child);24    }25  }26  return files;27}28 29console.log(countFilesIterative(tree));

Read the loop line by line:

1. Line 14: the array stack starts with the whole tree.
2. Line 16: the loop runs while the array still has work in it.
3. Line 17: pop() takes the last item off the end of the array.
4. Lines 18 to 20: an item with no children is a file, so add one to files.
5. Lines 22 and 23: an item with children is a folder, so push each child onto the array for later.
6. Line 29: print 4, for index.html, logo.svg, app.js, and notes.txt.

A continuation is a callback that says what to do with an answer. In continuation-passing style (CPS for short), a function doesn't return its answer in the usual way. It receives a callback, often named done, and calls done(answer) instead.

1function sumCps(n, done) {2  if (n === 0) return done(0);3  return sumCps(n - 1, (smaller) => {4    return done(smaller + n);5  });6}7 8sumCps(4, (answer) => console.log(answer));

In plain words, line by line:

1. Line 1: sumCps takes a number n and a callback done.
2. Line 2: the base case. When n is 0, call done(0).
3. Lines 3 and 4: call sumCps with n - 1 and a new callback. When the smaller sum arrives as smaller, the new callback adds n and passes the total to the older done.
4. Line 8: start with 4 and a callback that prints the answer. It prints 10, which is 1 + 2 + 3 + 4.

This is the same idea as callbacks and, later, async code: you hand another piece of code the next thing to do.

Mutual recursion means two or more functions call each other in a circle. Each function has its own base case. Otherwise, it passes a smaller input to the other function.

function isEven(n) {
  if (n === 0) return true;
  return isOdd(n - 1);
}

function isOdd(n) {
  if (n === 0) return false;
  return isEven(n - 1);
}

console.log(isEven(4), isOdd(5));

isEven(4) calls isOdd(3). That calls isEven(2), then isOdd(1), then isEven(0), which returns true. Line 11 prints true true: 4 is even, and 5 is odd. Each call still adds a stack frame in V8, so a very large number can overflow. Use a loop when you don't control how big the number gets.

Memoization means saving a function's answer for an input, so a later call with the same input can reuse it. The saved answers are called a cache. It helps when a recursive function asks for the same smaller problem many times.

The Fibonacci numbers are a good example. Each one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21. To work out fib(8), you need fib(7) and fib(6). But fib(7) needs fib(6) too. Without a cache, the same numbers get worked out again and again.

const cache = new Map();
let calls = 0;

function fib(n) {
  calls = calls + 1;
  if (cache.has(n)) return cache.get(n);
  if (n < 2) return n;
  const answer = fib(n - 1) + fib(n - 2);
  cache.set(n, answer);
  return answer;
}

console.log(fib(8));
console.log(calls);

In plain words, line by line:

1. Line 1: cache is a Map from an input to its answer.
2. Line 2: calls counts how many times fib runs.
3. Line 6: if the answer for n is already saved, return it.
4. Line 7: the base case. fib(0) is 0, and fib(1) is 1.
5. Lines 8 and 9: work out the answer, then save it in the cache.
6. Line 13 prints 21, and line 14 prints 15.

Fifteen calls is far fewer than the 67 calls the same function makes without a cache. A cache key must describe the whole input. If the input can change, you also need a rule for when to throw saved answers away.

A cache is not the same as the seen map later in this lesson. A cache reuses an answer. A seen map only remembers which objects you already visited, so you don't go round the same loop in the data forever.

Recursive data is data that holds smaller pieces with the same shape. For example:

• An object can hold an array of objects.
• A Map can hold objects as its values.
• A comment can hold replies, which hold more replies.

A deep clone copies an object and everything inside it. The hard part is a cycle: data that points back to itself. After profile.self = profile, the self property points to the same object it lives in. A clone that just follows every property would go round that loop forever.

The fix is a WeakMap. A WeakMap is like a Map whose keys are objects. It doesn't stop those objects from being cleared out of memory when nothing else uses them. Here it is called seen, and it links each original object to its copy. A safe deep clone works in this order:

1. If the value is a primitive, such as a number or a string, return it as it is.
2. If seen already has this object, return the copy saved there.
3. Make a new, empty copy.
4. Save the pair "original, copy" in seen.
5. Only then, copy the children.

Step 4 must come before step 5. Then, when a child points back to the original, the clone finds it in seen and uses the copy.

The panel below runs the full helper. Use the buttons to compare it with structuredClone, the clone function built into browsers and Node.

1function deepClone(value, seen = new WeakMap()) {2  if (Object(value) !== value || typeof value === "function") return value;3  if (seen.has(value)) return seen.get(value);4  if (value instanceof Date) return new Date(value.getTime());5  if (value instanceof Map) {6    const clone = new Map();7    seen.set(value, clone);8    for (const [key, entry] of value) {9      clone.set(deepClone(key, seen), deepClone(entry, seen));10    }11    return clone;12  }13  if (Array.isArray(value)) {14    const clone = [];15    seen.set(value, clone);16    for (const item of value) clone.push(deepClone(item, seen));17    return clone;18  }19  const clone = Object.create(Object.getPrototypeOf(value));20  seen.set(value, clone);21  for (const key of Reflect.ownKeys(value)) {22    clone[key] = deepClone(value[key], seen);23  }24  return clone;25}26 27const profile = {28  name: "Ada",29  dates: [new Date("2020-01-02T00:00:00Z")],30  meta: new Map([["visits", 3]]),31};32profile.self = profile;33 34const copy = deepClone(profile);35console.log(copy !== profile);36console.log(copy.dates[0] instanceof Date);37console.log(copy.meta.get("visits"));38console.log(copy.self === copy);

In the custom clone, line by line:

1. Line 2: a primitive, or a function, comes back as it is.
2. Line 3: an object already in seen gives back its saved copy.
3. Line 4: a Date gets a new Date with the same time.
4. Lines 7, 15, and 20: a Map, an array, or a plain object saves its new copy in seen before its children are copied.
5. Line 32: profile.self = profile makes the cycle.
6. Lines 35 to 38 print true, true, 3, and true. The last one shows the copy's self points to the copy.

The table below compares the two ways to clone. Read each row as: the kind of value, what the custom clone does, and what structuredClone does.

Use structuredClone for plain data that it supports: arrays, objects, Dates, Maps, Sets, ArrayBuffers, and cycles. Write your own helper only when you need a special rule, for example for functions or class methods. Elements on a page are not plain data. Copy them with node.cloneNode(true) instead.

A deep equal helper walks through two values side by side. It checks that everything inside them matches. Before you write one, you must decide some rules. A set of rules like this is called a policy. You must answer questions like these:

• Should NaN ("not a number") count as equal to NaN?
• Should -0 count as equal to 0?
• Does the order of an object's keys matter?
• Does the order of an array's items matter?
• What happens when both values point back to themselves?

1function deepEqual(a, b, seen = new WeakMap()) {2  if (Object.is(a, b)) return true;3  if (a === null || b === null || typeof a !== "object" || typeof b !== "object") return false;4  const known = seen.get(a);5  if (known?.has(b)) return true;6  if (!known) seen.set(a, new WeakSet([b]));7  else known.add(b);8  if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b)) return false;9  if (a instanceof Date) return Object.is(a.getTime(), b.getTime());10  if (Array.isArray(a)) {11    if (!Array.isArray(b) || a.length !== b.length) return false;12    return a.every((item, index) => deepEqual(item, b[index], seen));13  }14  if (a instanceof Map) {15    if (!(b instanceof Map) || a.size !== b.size) return false;16    const aEntries = [...a.entries()];17    const bEntries = [...b.entries()];18    return aEntries.every(([key, value], index) => {19      return deepEqual(key, bEntries[index][0], seen) && deepEqual(value, bEntries[index][1], seen);20    });21  }22  const aKeys = Reflect.ownKeys(a);23  const bKeys = Reflect.ownKeys(b);24  if (aKeys.length !== bKeys.length) return false;25  const bKeySet = new Set(bKeys);26  for (const key of aKeys) {27    if (!bKeySet.has(key) || !deepEqual(a[key], b[key], seen)) return false;28  }29  return true;30}31 32const left = { a: NaN, b: -0, nested: [1, { x: 2 }] };33const right = { nested: [1, { x: 2 }], b: 0, a: NaN };34console.log(deepEqual(left, right));35right.b = -0;36console.log(deepEqual(left, right));37left.self = left;38right.self = right;39console.log(deepEqual(left, right));40console.log(deepEqual([1, 2], [2, 1]));

This lesson's helper uses these rules:

• Line 2 uses Object.is. It works like ===, except in two cases: it says NaN equals NaN, and it says -0 is different from 0.
• Object keys are matched by name, so their order doesn't matter.
• Array items are matched by position, so their order does matter.
• Lines 4 to 7 handle cycles. A WeakMap links each left object to a WeakSet, a set of the right objects it was already compared with. If the same pair comes up again, the helper says they are equal instead of going round the loop forever.

Where you'll use advanced recursion

You'll need these tools whenever front-end code walks through nested data and you don't know how deep it goes:

• Walking a folder of files that a user drags onto the page, to show the totals.
• Walking a tree of page elements in tests or in a text editor, when you can't trust its depth.
• Showing comment threads where replies hold more replies.
• Tidying up deeply nested JSON that a server sends back.
• Copying data before you send it to a worker or an iframe.
• Comparing two snapshots of a form, so a different key order doesn't look like a change.

The table below helps you pick a tool. Read each row as: the tool, what it does, and when it helps.

Common misconceptions

The table below lists four more wrong guesses. Read each row as: the guess, what is really true, and what to do instead.

For each code question, ask three things. Is any work left after the call? Is a thunk still waiting for the loop? Which equality rules does the helper use? Each answer explains why it is right or wrong.

Key takeaways

• A tail call is the last thing a function does. But most JavaScript engines still add a stack frame for it.
• A trampoline stops stack overflows: each step returns a thunk, and a loop calls the thunks one at a time.
• An explicit stack, an array plus a loop, is often the clearest way to walk a tree of unknown depth.
• CPS passes a callback that says what to do next. It is the same idea as callbacks and async code.
• Deep clone and deep equal need a seen map, usually a WeakMap, so data that points back to itself doesn't trap them.

Coming next: Transducers, functors & monads. There, you will work with values that you can map over and chain, step by step.