JavaScript Recursion

Recursion means a function calls itself. It is a natural fit for problems that break into smaller copies of the same problem.

Every recursive function needs two things:

1. a base case: a situation simple enough to answer directly (this stops the recursion), and
2. a recursive case: the function calls itself with a smaller problem.

Counting down

1
2
3
4
5
6
7
8
9
10

function countdown(n) {
  if (n === 0) {          // base case
    console.log("Liftoff!");
    return;
  }
  console.log(n);
  countdown(n - 1);       // recursive case
}

countdown(3);

Factorial

5! = 5 × 4 × 3 × 2 × 1. And n! = n × (n - 1)!.

1
2
3
4
5
6

function factorial(n) {
  if (n <= 1) return 1;            // base case
  return n * factorial(n - 1);     // recursive case
}

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

Trace it: factorial(3) → 3 * factorial(2) → 3 * 2 * factorial(1) → 3 * 2 * 1 → 6.

A practical use: nested data

Recursion shines with trees, such as nested comments or folders.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

const menu = [
  { name: "Home" },
  { name: "Products", children: [
      { name: "Books" },
      { name: "Games", children: [{ name: "Board games" }] }
  ] }
];

function countItems(items) {
  let total = 0;
  for (const item of items) {
    total += 1;
    if (item.children) {
      total += countItems(item.children);
    }
  }
  return total;
}

console.log(countItems(menu)); // → 5

Danger: no base case

1
2
3

function broken() {
  broken();    // never stops
}

Each call is stored on the call stack. Without a base case, the stack fills up and JavaScript throws RangeError: Maximum call stack size exceeded. (Do not run that in the editor.)

Recursion or loop?

Anything recursive can be written with a loop, and loops are usually faster and use less memory. Use recursion when it makes the code clearer, as with nested structures. For simple repetition, a loop is the better choice.