Learn/JavaScript/11. Recursion
Lesson 11 of 15
Sign in

JavaScript, lesson 11

Recursion

A recursive function is one that calls itself. That sounds like a loop that never ends, but it works because each call handles a smaller version of the problem, and one very small version is answered directly. Recursion is the natural fit for data that contains smaller data of the same shape: folders inside folders, comments with replies, arrays nested inside arrays.

The two parts

Every recursive function needs:

  1. A base case: an input so simple you can answer it without recursion.
  2. A recursive case: break the input into a smaller piece, call the function on that, and combine the answer.

Follow it by hand: sumTo(4) is 4 + sumTo(3), which is 4 + 3 + sumTo(2), and so on until sumTo(0) returns 0. Then the waiting additions finish one by one: , , , , .

2 exercises to try what you just read.

Exercise 1

Nested gift boxes

Press Ctrl Enter or Check to test your code.

Exercise 2

Staircase climbing

Press Ctrl Enter or Check to test your code.

0
1
3
6
10

The call stack

Each call that has not finished yet waits on the call stack, with its own copy of its parameters and local variables. That is why n can be 4 in one call and 3 in another at the same time. The stack has a limit; in Node.js it allows roughly ten thousand nested calls, depending on how much each call stores. Go past it and you get RangeError: Maximum call stack size exceeded. Forgetting the base case, or a recursive call that does not get smaller, leads straight there.

For a simple count like sumTo, a loop is better. Recursion shines when the shape of the data branches.

Recursion on nested data

Here is a function that counts every number in an array whose elements may themselves be arrays, to any depth:

You do not need to picture every level. Trust that the recursive call correctly handles a smaller piece (the leap of faith), and only check that the base case is right and that combining the pieces is right.

Branching recursion

Some problems split into several smaller problems. Generating all strings of n coin flips splits into "those starting with H" and "those starting with T":

Branching recursion can be slow when the same subproblem is solved again and again (naive Fibonacci is the classic example). Storing answers you have already computed in a Map fixes that; this trick is called memoization.

Big results

Recursive problems such as factorials produce huge numbers quickly. Regular numbers stay exact only up to Number.MAX_SAFE_INTEGER (about 9 quadrillion). For larger whole numbers use BigInt: write literals with an n suffix (20n) or convert with BigInt(x). You cannot mix BigInt and regular numbers in arithmetic without converting one of them.

Further reading

  • MDN: Functions guide, recursion
  • MDN: Recursion (glossary)
  • MDN: BigInt
  • MDN: Array.isArray

A gift is described as a JSON array. Numbers are the values of gifts; arrays are boxes that can contain gifts and other boxes. Write recursive code to print two lines:

  • total N: the sum of all numbers at every depth;
  • depth D: the deepest nesting level, where the outer array is level 1 and an empty array still counts as a level.

The input is one line of JSON.

Sample input:

Sample output:

You climb a staircase of N steps, taking either 1 or 2 steps at a time. How many different ways are there to reach the top? For 3 steps there are 3 ways: 1+1+1, 1+2 and 2+1.

Write a recursive function ways(n): there is 1 way to climb 0 steps (do nothing) and 1 way to climb 1 step; for more steps, the first move is either 1 step (leaving n - 1) or 2 steps (leaving n - 2). Use a Map to remember results you have already computed, otherwise large inputs will be far too slow. Return a BigInt so that the answer stays exact.

The input is one whole number N with 0 <= N <= 300. Print the number of ways.

Sample input:

Sample output:

function sumTo(n) {
  if (n === 0) return 0;          // base case
  return n + sumTo(n - 1);        // recursive case: a smaller problem
}
console.log(sumTo(4));            // 10
function countNumbers(value) {
  if (!Array.isArray(value)) {
    return typeof value === "number" ? 1 : 0;   // base case: a single value
  }
  let count = 0;
  for (const item of value) {
    count += countNumbers(item);                // recurse into each element
  }
  return count;
}

console.log(countNumbers([1, [2, 3, [4]], "x", [[5]]]));   // 5
function flips(n) {
  if (n === 0) return [""];
  const shorter = flips(n - 1);
  return [...shorter.map((s) => "H" + s), ...shorter.map((s) => "T" + s)];
}
console.log(flips(2));   // [ 'HH', 'HT', 'TH', 'TT' ]
[5, [10, [1, 2]], []]
total 18
depth 3
3
3