Recursion

Table of Contents

1. A Function That Calls Itself
2. The Two Parts of Every Recursion
3. Watching the Call Stack
4. Stack Overflow
5. Where You Meet Recursion at Work
6. Thinking Recursively
7. The Fibonacci Trap and Memoization
8. Recursion vs Loops
9. Divide and Conquer: Fast Power
10. Backtracking: Subsets, Permutations, Parentheses
11. Recipe: recursion.ts for algolab
12. Try It Yourself

1. A Function That Calls Itself

Russian nesting dolls: open the big doll and inside is a smaller doll that opens the same way, and inside that is a smaller one, until you reach a tiny doll that does not open. To count the dolls you could say: "the number of dolls is one (this doll) plus the number of dolls inside it". That sentence defines the answer in terms of the same question on a smaller problem. It stops at the tiny doll.

That is recursion: a function that solves a problem by calling itself on a smaller version of the problem, until the problem is so small the answer is obvious.

Recursion feels odd at first, and many people find it harder than loops. It becomes natural once you trust one rule: assume the function already works for smaller inputs, and just use it. This chapter builds that habit with small examples, then uses it for problems where loops get messy: nested data, trying every combination, and splitting a problem in half. Trees and graphs in later chapters are almost impossible to handle without it.

2. The Two Parts of Every Recursion

Every working recursive function has exactly two parts:

1. A base case: an input so small that the function returns the answer directly, with no further call.
2. A recursive case: the function calls itself on a smaller input and uses that answer to build its own.

The classic example is factorial. 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!. The big problem contains a smaller copy of itself:

function factorial(n: number): number {
  if (n < 0) throw new RangeError("n must be 0 or more");
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case: a smaller problem
}

console.log(factorial(5)); // 120

The two parts pull in different directions. The recursive case must move toward the base case on every call. Here n goes down by one, so n eventually reaches 1. If you forgot to shrink the input, or wrote a base case that can never be reached (say n === 0 and you call with n = 5.5), the function would call itself forever.

A checklist for any recursive function:

• What is the base case? Is every input able to reach it?
• Does each recursive call get a smaller problem?
• If I trust the recursive call to be correct, is my combining step correct?

That last question is the leap of faith. For factorial: "if factorial(n - 1) is correct, then n * factorial(n - 1) is correct." That is enough. You never have to hold all the calls in your head at once.

3. Watching the Call Stack

In the previous chapter you learned that the call stack holds one frame per active function call. Recursion makes that stack visible. Here is factorial(3) step by step:

factorial(3)
  = 3 * factorial(2)
          = 2 * factorial(1)
                  = 1               <- base case reached
          = 2 * 1  = 2
  = 3 * 2  = 6

As a stack of frames, growing downward, and then shrinking:

call:      factorial(3)  waiting for factorial(2)
call:        factorial(2)  waiting for factorial(1)
call:          factorial(1)  returns 1
return:      factorial(2)  returns 2 * 1 = 2
return:    factorial(3)  returns 3 * 2 = 6

Each frame remembers its own n and where it was in the calculation. Frames are pushed as the function goes deeper, and popped as answers return. Nothing about this is special: it is the ordinary call stack, just with the same function many times over.

Two numbers describe the cost:

• Time: how many calls happen in total. For factorial(n), n calls, so O(n).
• Space: how deep the stack gets. For factorial(n), n frames at the deepest point, so O(n) space, even though we never create an array. This hidden space cost is easy to forget.

4. Stack Overflow

The call stack has a limited size. If recursion goes too deep, the engine gives up with an error. Try summing the numbers from 1 to a million:

function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}

console.log(sumTo(100)); // 5050

try {
  sumTo(1_000_000);
} catch (e) {
  console.log((e as Error).name, (e as Error).message);
}
// RangeError Maximum call stack size exceeded

The exact limit depends on the engine and on how much each frame stores. In Node.js it is usually around ten thousand frames or more for simple functions, so sumTo(5000) works but a million does not.

You will meet this error in two situations:

1. A bug: a missing or unreachable base case. The recursion never stops and the stack overflows quickly.
2. A legitimately deep input: such as a list with a million items or a linked structure that is very deep.

For the second case you have two fixes. Rewrite the recursion as a loop (possibly with your own Stack from the last chapter), or limit the depth of the input. JavaScript engines do not reliably perform "tail call optimization", where a call in the last position reuses the frame, so do not count on it. The loop version never overflows:

function sumToLoop(n: number): number {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

console.log(sumToLoop(1_000_000)); // 500000500000

(And in this particular case, the formula n * (n + 1) / 2 from Math for Programmers does it in O(1).)

5. Where You Meet Recursion at Work

• Nested data. The file system (folders inside folders), the DOM (elements inside elements), JSON with nested objects, comment threads with replies to replies, and menus with submenus are all naturally recursive. A function that handles one level and calls itself for the children handles any depth.
• Parsers and compilers. A parenthesized expression contains smaller expressions.
• Divide and conquer. Merge sort, quick sort, and binary search all split a problem into smaller copies of itself.
• Trees and graphs. Depth-first search is recursion, as you will see in the trees and graphs chapters.
• Search and puzzles. Solving Sudoku, finding all routes, generating all combinations: try a choice, recurse, undo the choice (backtracking, later in this chapter).
• Deep copy and comparison. structuredClone, deep equality in test libraries, and JSON serializers all recurse into nested values.

6. Thinking Recursively

A good habit is to answer these questions in order before writing code:

1. What is the smallest input, and what is its answer? (Base case.)
2. How can I make the input one step smaller?
3. If I had the answer for the smaller input, how do I get the answer for this one?

Example: is a string a palindrome? The smallest strings are the empty string and a single letter: both are palindromes. For a longer string, compare the first and last characters. If they differ, it is not a palindrome. If they match, the answer depends on whether the middle part (without those two characters) is a palindrome.

function isPalindrome(s: string): boolean {
  if (s.length < 2) return true; // base case
  if (s[0] !== s[s.length - 1]) return false;
  return isPalindrome(s.slice(1, -1)); // smaller problem
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("abca")); // false

(slice copies the string on every call, so this is O(n squared) in the worst case. A loop with two pointers from the arrays chapter is better in practice. The recursive version is for learning the pattern.)

Example: flatten a nested array. [1, [2, [3, [4]], 5]] should become [1, 2, 3, 4, 5]. We do not know how deep the nesting goes, which makes a plain loop awkward. Recursion: for each item, if it is a number, keep it. If it is an array, flatten that array and keep the results.

type Nested<T> = T | Nested<T>[];

function flatten<T>(items: Nested<T>[]): T[] {
  const out: T[] = [];
  for (const item of items) {
    if (Array.isArray(item)) out.push(...flatten(item as Nested<T>[]));
    else out.push(item as T);
  }
  return out;
}

console.log(JSON.stringify(flatten([1, [2, [3, [4]], 5]])));
// [1,2,3,4,5]

The base case is hidden: an array with no nested arrays just never makes a recursive call. Many recursive functions on nested data look like this. JavaScript has a built-in arr.flat(Infinity) that does the same job.

7. The Fibonacci Trap and Memoization

The Fibonacci numbers run 0, 1, 1, 2, 3, 5, 8, 13, ..., where each one is the sum of the two before it. The definition is already recursive, so the code writes itself:

function fibSlow(n: number): number {
  if (n < 2) return n; // base cases: fib(0) = 0, fib(1) = 1
  return fibSlow(n - 1) + fibSlow(n - 2);
}

It is correct, and it is a disaster. Count how many times the function is called:

Every step up in n multiplies the number of calls by about 1.6. That is exponential growth, roughly O(2 to the power n), which you met in the Big-O chapter. fibSlow(40) takes about half a second on a laptop, and fibSlow(50) takes a minute or more.

Why so many calls? Look at the tree of calls for fib(5):

                      fib(5)
                    /        \
              fib(4)          fib(3)
             /      \         /     \
        fib(3)    fib(2)   fib(2)   fib(1)
        /   \
    fib(2) fib(1)  ...

fib(3) is calculated twice, fib(2) three times, and the repetition snowballs. The function keeps solving the same subproblem over and over.

The fix is memoization: remember each answer the first time, and reuse it. A Map is perfect (the hash map chapter): key n, value fib(n).

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(50)); // 12586269025

Now each n is calculated once, so there are only about n real computations: O(n) time, with O(n) space for the map and the stack. The same call that took a minute is instant. Nothing about the logic changed. We only stopped repeating work.

Memoization works for any pure function: one that always returns the same output for the same input and has no side effects. You can write it once as a wrapper:

function memoize<A extends unknown[], R>(
  fn: (...args: A) => R,
): (...args: A) => R {
  const cache = new Map<string, R>();
  return (...args: A): R => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

React's useMemo, caching of expensive API calculations, and the lodash.memoize helper are all this idea. Be careful with memory: a cache that never evicts old entries is a memory leak waiting for production. This is the seed of dynamic programming, which gets its own chapter later.

8. Recursion vs Loops

Anything recursive can be written as a loop, and the other way around. Which should you use?

function fibLoop(n: number): number {
  let a = 0;
  let b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

fibLoop runs in O(n) time and O(1) space. It has no stack depth problem and no map. For Fibonacci, the loop wins.

Rule of thumb:

• If the data is flat or the work is a simple accumulation, use a loop.
• If the data is nested or branching (a tree, a graph, "try every option"), recursion is usually clearer, and a loop would need your own stack to remember where you were.
• If the depth could be huge (hundreds of thousands), prefer a loop with an explicit stack.

In interviews, solving a problem recursively is often accepted. Be ready for the follow-up, "what happens with a very deep input?", and be able to say "the call stack could overflow, so I would convert it to a loop with my own stack".

9. Divide and Conquer: Fast Power

Recursion is also a way to halve a problem. To compute 2^10 with a loop you multiply ten times. But 2^10 = (2^5)^2, and 2^5 = 2 × (2^2)^2. Halving the exponent each time needs only about log2(n) steps:

function power(base: number, exp: number): number {
  if (exp === 0) return 1;
  const half = power(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

console.log(power(2, 10)); // 1024
console.log(power(3, 5)); // 243

Compute half once and reuse it. If you wrote power(base, e / 2) * power(base, e / 2), you would calculate the same thing twice and lose the whole benefit. That is the Fibonacci mistake in disguise.

Trace power(2, 10):

It takes O(log n) time and O(log n) stack depth. Halving the problem every step is the same idea behind binary search (next chapters) and merge sort. Whenever you see a recursion that halves the input, expect log n depth.

10. Backtracking: Subsets, Permutations, Parentheses

Backtracking is recursion for "try every possibility": make a choice, explore everything that follows from it, then undo the choice and try the next one. Think of walking a maze and returning to the last fork when you hit a dead end. It generates combinations, solves puzzles such as Sudoku and the N-Queens problem, and powers search with rules.

The pattern is always the same:

explore(state):
  if state is a complete answer: save a copy, return
  for each choice available now:
    make the choice
    explore(new state)
    undo the choice

Subsets

All subsets of [1, 2, 3] (the "power set"): for each item you either leave it out or take it. That is two choices per item, so there are 2^n subsets.

function subsets<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];

  function explore(i: number): void {
    if (i === items.length) {
      result.push([...current]); // save a COPY
      return;
    }
    explore(i + 1); // leave items[i] out
    current.push(items[i]); // choose it
    explore(i + 1);
    current.pop(); // un-choose (backtrack)
  }

  explore(0);
  return result;
}

console.log(JSON.stringify(subsets([1, 2, 3])));
// [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

Two details cause most bugs:

1. Save a copy with [...current]. If you push current itself, every saved result points to the same array, and they all end up empty after the final pop.
2. Undo exactly what you did. The pop() after the second recursive call undoes the push. Forget it and the state leaks into the next branch.

The choices form a tree, where each level decides one more item:

                    []
         leave 1 /      \ take 1
               []        [1]
        leave 2/  \take 2     ...

Permutations

All orderings of [1, 2, 3]: there are n! of them (6 for three items). At each position, try every item not yet used.

function permutations<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];
  const used = new Array<boolean>(items.length).fill(false);

  function explore(): void {
    if (current.length === items.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(items[i]);
      explore();
      current.pop();
      used[i] = false;
    }
  }

  explore();
  return result;
}

console.log(JSON.stringify(permutations([1, 2, 3])));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

The used array records which items are already in current. The three lines "mark, push, recurse" and the three that follow, "pop, unmark", mirror each other. That symmetry is how you keep backtracking code correct.

Generating valid parentheses

Problem: list all strings with n pairs of correctly matched parentheses. For n = 3: ((())), (()()), (())(), ()(()), ()()().

Naive approach: generate every string of ( and ) and filter. That is 2^(2n) strings. Backtracking is smarter: it prunes, meaning it never builds a branch that cannot succeed. The rules are:

• You may add ( while you have used fewer than n of them.
• You may add ) only if there are more ( than ) so far.

function generateParentheses(n: number): string[] {
  const result: string[] = [];

  function build(text: string, open: number, close: number): void {
    if (text.length === 2 * n) {
      result.push(text);
      return;
    }
    if (open < n) build(text + "(", open + 1, close);
    if (close < open) build(text + ")", open, close + 1);
  }

  build("", 0, 0);
  return result;
}

console.log(generateParentheses(3).join(" "));
// ((())) (()()) (())() ()(()) ()()()

Strings are immutable, so text + "(" makes a new string for each call. There is nothing to undo, which is why this version has no pop. Pruning is the big idea: stop exploring as soon as you know a path is hopeless.

Towers of Hanoi

One more classic. Move n disks from peg A to peg C, one at a time, never putting a larger disk on a smaller one, using peg B as a spare. The recursive insight: to move n disks, first move n - 1 out of the way, move the biggest, then move the n - 1 back on top.

function hanoi(n: number, from = "A", to = "C", via = "B"): string[] {
  if (n === 0) return [];
  return [
    ...hanoi(n - 1, from, via, to),
    `${from}->${to}`,
    ...hanoi(n - 1, via, to, from),
  ];
}

console.log(hanoi(3).join(" "));
// A->C A->B C->B A->C B->A B->C A->C

It always takes 2^n - 1 moves: 7 for three disks. Nobody can do better, and the legend says that moving 64 disks would take longer than the age of the universe.

How big is the search?

Backtracking can be expensive, because the answer itself is huge:

Ten items give 1,024 subsets and 3,628,800 permutations. Twenty items give over a million subsets and more permutations than you could ever enumerate. When the interviewer asks for "all" of something, the answer is exponential by nature. Mention it, and use pruning to avoid exploring branches you do not need.

11. Recipe: recursion.ts for algolab

Create src/recursion.ts and collect all the functions from this chapter:

export function factorial(n: number): number {
  if (n < 0) throw new RangeError("n must be 0 or more");
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // smaller problem
}

export function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}

export function sumToLoop(n: number): number {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

export function power(base: number, exp: number): number {
  if (exp === 0) return 1;
  const half = power(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

export function isPalindrome(s: string): boolean {
  if (s.length < 2) return true;
  if (s[0] !== s[s.length - 1]) return false;
  return isPalindrome(s.slice(1, -1));
}

export function fibSlow(n: number): number {
  if (n < 2) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

export function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

export function fibLoop(n: number): number {
  let a = 0;
  let b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

export function memoize<A extends unknown[], R>(
  fn: (...args: A) => R,
): (...args: A) => R {
  const cache = new Map<string, R>();
  return (...args: A): R => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

export type Nested<T> = T | Nested<T>[];

export function flatten<T>(items: Nested<T>[]): T[] {
  const out: T[] = [];
  for (const item of items) {
    if (Array.isArray(item)) out.push(...flatten(item as Nested<T>[]));
    else out.push(item as T);
  }
  return out;
}

export function subsets<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];

  function explore(i: number): void {
    if (i === items.length) {
      result.push([...current]);
      return;
    }
    explore(i + 1); // leave items[i] out
    current.push(items[i]); // choose it
    explore(i + 1);
    current.pop(); // un-choose (backtrack)
  }

  explore(0);
  return result;
}

export function permutations<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];
  const used = new Array<boolean>(items.length).fill(false);

  function explore(): void {
    if (current.length === items.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(items[i]);
      explore();
      current.pop();
      used[i] = false;
    }
  }

  explore();
  return result;
}

// All valid strings with n pairs of parentheses
export function generateParentheses(n: number): string[] {
  const result: string[] = [];

  function build(text: string, open: number, close: number): void {
    if (text.length === 2 * n) {
      result.push(text);
      return;
    }
    if (open < n) build(text + "(", open + 1, close);
    if (close < open) build(text + ")", open, close + 1);
  }

  build("", 0, 0);
  return result;
}

export function hanoi(n: number, from = "A", to = "C", via = "B"): string[] {
  if (n === 0) return [];
  return [
    ...hanoi(n - 1, from, via, to),
    `${from}->${to}`,
    ...hanoi(n - 1, via, to, from),
  ];
}

And the tests, in src/recursion.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  factorial, sumTo, sumToLoop, power, isPalindrome, fibSlow, fibMemo, fibLoop,
  memoize, flatten, subsets, permutations, generateParentheses, hanoi,
} from "./recursion.ts";

test("factorial", () => {
  assert.equal(factorial(0), 1);
  assert.equal(factorial(5), 120);
  assert.throws(() => factorial(-1), RangeError);
});

test("sumTo matches the loop", () => {
  assert.equal(sumTo(100), 5050);
  assert.equal(sumTo(100), sumToLoop(100));
});

test("power", () => {
  assert.equal(power(2, 10), 1024);
  assert.equal(power(3, 5), 243);
  assert.equal(power(7, 0), 1);
});

test("isPalindrome", () => {
  assert.equal(isPalindrome("racecar"), true);
  assert.equal(isPalindrome("abca"), false);
  assert.equal(isPalindrome(""), true);
});

test("three fibonaccis agree", () => {
  for (let n = 0; n <= 20; n++) {
    assert.equal(fibSlow(n), fibLoop(n));
    assert.equal(fibMemo(n), fibLoop(n));
  }
  assert.equal(fibMemo(50), 12586269025);
});

test("memoize caches", () => {
  let calls = 0;
  const square = memoize((n: number) => {
    calls++;
    return n * n;
  });
  assert.equal(square(4), 16);
  assert.equal(square(4), 16);
  assert.equal(calls, 1);
});

test("flatten", () => {
  assert.deepEqual(flatten([1, [2, [3, [4]], 5]]), [1, 2, 3, 4, 5]);
});

test("subsets", () => {
  const result = subsets([1, 2, 3]);
  assert.equal(result.length, 8);
  assert.deepEqual(result[0], []);
  assert.deepEqual(result[7], [1, 2, 3]);
});

test("permutations", () => {
  const result = permutations([1, 2, 3]);
  assert.equal(result.length, 6);
  assert.deepEqual(result[0], [1, 2, 3]);
  assert.deepEqual(result[5], [3, 2, 1]);
});

test("generateParentheses", () => {
  assert.deepEqual(generateParentheses(3), ["((()))", "(()())", "(())()", "()(())", "()()()"]);
});

test("hanoi", () => {
  assert.equal(hanoi(3).length, 7);
  assert.deepEqual(hanoi(2), ["A->B", "A->C", "B->C"]);
});

Run them:

npx tsx --test

Then try a few calls in demo.ts:

import { factorial, sumTo, power, fibMemo, fibLoop, permutations, hanoi } from "./src/recursion";

console.log(factorial(5), sumTo(100), power(2, 10));
console.log(fibMemo(50), fibLoop(50));
console.log(permutations([1, 2, 3]).length);
console.log(hanoi(3).join(" "));

npx tsx demo.ts

120 5050 1024
12586269025 12586269025
6
A->C A->B C->B A->C B->A B->C A->C

To feel the exponential blow-up yourself, time fibSlow(35), fibSlow(38), and fibSlow(40) with performance.now() as in the first chapter. Each step of two in n should roughly multiply the time by 2.6. Then time fibMemo(40) and notice that you cannot even measure it.

12. Try It Yourself

1. Sum of digits. Write sumDigits(n) recursively, so that sumDigits(1234) is 10. What is the base case? (Hint: the last digit is n % 10, and the rest is Math.floor(n / 10), an idea from Modular Arithmetic.)
2. Count down and up. Write countdown(n) that prints n down to 1 and then "liftoff". Then change only the order of two lines so it prints 1 up to n instead. What does this tell you about when the work happens relative to the recursive call?
3. Deep object walk. Write countLeaves(value) that counts the non-object values in a nested object like { a: 1, b: { c: 2, d: { e: 3, f: 4 } } }. The answer is 4. Then write maxDepth(value) that returns how deep it goes (3 here).
4. Climbing stairs (interview). You can climb 1 or 2 stairs at a time. How many different ways are there to climb n stairs? Write it recursively (the answer for 4 stairs is 5), watch it become slow for n = 40, then fix it with memoize. Notice that the recurrence is the same as Fibonacci.
5. Combinations (interview). Write combinations(items, k) that returns all subsets of exactly size k. For [1, 2, 3, 4] and k = 2 there are 6 results. Reuse the subsets skeleton, and prune a branch as soon as current already has k items, or when there are not enough items left to reach k.
6. Letter combinations (interview). On a phone keypad, 2 is "abc" and 3 is "def". Given "23", return all letter combinations: ad ae af bd be bf cd ce cf. Which backtracking pattern fits?
7. Convert to a loop. Rewrite sumTo as a loop that uses your own Stack, pushing numbers instead of making calls. This is the general recipe for turning any recursion into a loop.

Recursion splits a problem into smaller copies and trusts the smaller copies to work. Next we apply the idea of halving to searching. In Searching you meet binary search, the algorithm that finds one item among a million in about twenty steps, and one of the easiest to get subtly wrong.