Advanced recursion

Recursion after the basics

The beginner Recursion lesson taught the base case, the recursive case, and why the call stack grows while calls wait. This lesson starts from there. We will not repeat nesting dolls and simple factorial. Instead, we will ask: what if the input is 100,000 levels deep, or the data points back to itself?

Advanced recursion means controlling the shape of recursive work. Sometimes you rewrite the function so the recursive call is the final action. Sometimes you return a thunk and let a loop run it. Sometimes you stop using recursive calls entirely and keep your own stack in an array. For recursive data, you also remember objects you have already seen.

You will connect these ideas to stack and heap, closures, WeakMap and WeakSet, and messaging and cloning with structuredClone.

A call is in tail position when its result is returned directly. Compare the two factorials below. Line 3 in the first function is not tail position because n * still waits for the recursive answer. Line 8 in the accumulator version is tail position because the next call receives the updated product and no multiply remains.

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));

Step through the accumulator version. Watch acc become 1, then 5, then 20, then 60, then 120. That is the pending multiplication moved into an argument.

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 snippet deliberately throws in Chrome and Node. It is tail-recursive and strict, but V8 still grows the stack. The exact depth varies, so the example uses a large number and asks only for the error, not for a magic limit.

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

A thunk is a function with no arguments that delays work. A trampoline is a loop that keeps calling thunks until the result is not a function. Instead of nesting sumThunk(5) inside sumThunk(4) inside sumThunk(3), each call returns the next thunk to 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: current starts as a function, line 4 asks whether it is still a function, line 5 calls exactly one thunk, and line 6 counts that turn. When a number appears, line 8 returns it.

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);

The safest production rewrite is often not clever. Put pending work in an array, then loop until that array is empty. The heap holds the array; the JavaScript call stack stays one frame deep. This is exactly what you want for a file tree, a DOM walk, a sitemap import, or user-generated comment threads with unknown depth.

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));

In continuation-passing style, a function does not return its final answer to its caller in the usual way. It receives a callback, often named done or cont, and calls that callback with the answer. The callback is the continuation: the rest of the program written as a value.

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));

Line 2 says the base case should call done(0). Line 3 passes a new continuation to the smaller problem. That continuation says: when the smaller sum arrives, add the current n, then call the older continuation. This is the same mental model behind callbacks and later async code: give another piece of code the next thing to do.

Recursive data contains smaller values with the same shape. An object can contain an array of objects; a Map can point to objects; a comment can contain replies that contain replies. The challenge is cycles: profile.self = profile points back to the object you started from.

A safe deep clone handles primitives directly, creates the destination container early, stores the source-to-copy pair in a WeakMap, then clones children. The early store is what makes cycles work.

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);

Prefer structuredClone for plain structured data that the platform supports: arrays, objects, Dates, Maps, Sets, ArrayBuffers, and cycles. Reach for a custom helper when you need a specific policy for functions, prototypes, descriptors, or values the structured clone algorithm rejects. DOM nodes are live host objects; clone them with DOM APIs, not this data helper.

A deep equal helper walks two values together. It needs to answer policy questions before it touches recursion: should NaN equal NaN? Should -0 equal 0? Does object key order matter? Are arrays ordered? What happens when both sides 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]));

The helper in this lesson uses Object.is, so NaN matches itself and -0 remains different from 0. Object property order does not matter: keys are matched by identity and name. Array order does matter because index position is part of the value. Cycles are handled by a WeakMap from left objects to a WeakSet of right objects already compared with them.

Where you’ll use advanced recursion

These techniques show up whenever front-end code walks unknown nested data:

• Walking a file tree from a drag-and-drop upload before showing totals.
• Traversing a DOM-like tree in tests or a content editor without trusting its depth.
• Rendering comment threads where replies can contain more replies.
• Normalizing deeply nested JSON returned by an API.
• Cloning message payloads before sending them to workers or iframes.
• Comparing form snapshots in state-management tools without false positives from key order.

Common misconceptions

Key takeaways

• Tail position means no work remains after the call, but most JavaScript engines still do not reuse the frame.
• Trampolines make recursive steps stack-safe by returning thunks and running them in a loop.
• Explicit stacks are often the clearest production answer for unknown-depth trees.
• CPS turns “what happens next” into a callback, which connects recursion to callback and async patterns.
• Deep clone and deep equal need a seen-pair structure, usually a WeakMap, to handle cycles honestly.

Up next: Functors and monads, where functional patterns move from recursive control flow to values that map, chain, and carry context.