Recursion

A recursive function is one that calls itself. It solves a problem by solving a smaller version of the same problem, until the problem is so small the answer is obvious. Some problems are naturally recursive: anything shaped like a tree (folders inside folders, comments with replies, menus with submenus) and many maths definitions (a factorial is a number times the factorial of the number below it).

The two parts every recursive function needs

1. A base case: the smallest version of the problem, answered directly, without calling itself. This is what stops the recursion.
2. A recursive case: the function calls itself on a smaller input, moving towards the base case.

function countdown(n) {
  if (n === 0) {                 // base case: stop here
    console.log("Lift off!");
    return;
  }
  console.log(n);
  countdown(n - 1);              // recursive case: a smaller problem
}
countdown(3);

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0), which hits the base case and stops.

Factorial

5! (five factorial) is 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!, 4! = 4 × 3!, and so on, down to 1! = 1. That definition is the code:

function factorial(n) {
  if (n <= 1) return 1;            // base case
  return n * factorial(n - 1);     // recursive case
}
console.log(factorial(5), factorial(10));

Tracing it on the call stack

Every call waits for the one it made to finish. JavaScript keeps track of the waiting calls on the call stack: each new call goes on top, and when one returns, it comes off and the call below carries on:

Read the table top to bottom for the calls going down, then bottom to top for the answers coming back up. Logging with indentation shows the same thing:

function factorialTrace(n, depth = 0) {
  const pad = "  ".repeat(depth);
  console.log(`${pad}factorial(${n})`);
  const result = n <= 1 ? 1 : n * factorialTrace(n - 1, depth + 1);
  console.log(`${pad}-> ${result}`);
  return result;
}
factorialTrace(4);

More classic recursive programs

// the sum of the digits of a number: 4096 -> 4 + 0 + 9 + 6
function digitSum(n) {
  if (n < 10) return n;
  return (n % 10) + digitSum(Math.floor(n / 10));
}

// a to the power b, for whole b >= 0
function power(a, b) {
  if (b === 0) return 1;
  return a * power(a, b - 1);
}

// reverse a string: the last character, then the reverse of the rest
function reverse(text) {
  if (text.length <= 1) return text;
  return text.at(-1) + reverse(text.slice(0, -1));
}

// add up 1 to n
function sumTo(n) {
  return n === 0 ? 0 : n + sumTo(n - 1);
}

// is it a palindrome? compare the ends, then check the middle
function isPalindrome(text) {
  if (text.length <= 1) return true;
  if (text[0] !== text.at(-1)) return false;
  return isPalindrome(text.slice(1, -1));
}

console.log(digitSum(4096), power(2, 10), reverse("recursion"), sumTo(100));
console.log(isPalindrome("racecar"), isPalindrome("rocket"));

Each one has the same shape: answer the tiny case directly, otherwise do one small step and let a recursive call handle the rest.

Fibonacci, and why the simple version is slow

In the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13...) each number is the sum of the two before it. The recursive definition is short:

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}
console.log([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10].map(fib));

But each call makes two calls, so the work doubles at every level: fib(30) makes over a million calls, mostly recalculating the same values. The fix is memoisation: remember answers you've already worked out.

let calls = 0;
function slowFib(n) {
  calls++;
  return n < 2 ? n : slowFib(n - 1) + slowFib(n - 2);
}
slowFib(25);
console.log("simple version, fib(25):", calls, "calls");

const memo = new Map();
calls = 0;
function fastFib(n) {
  calls++;
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);    // already worked out
  const value = fastFib(n - 1) + fastFib(n - 2);
  memo.set(n, value);
  return value;
}
console.log("memoised, fib(25):", fastFib(25), "in", calls, "calls");

Where recursion shines: nested data

Loops handle flat lists well, but data nested to unknown depth is natural for recursion: the function handles one level and calls itself for anything nested inside:

// flatten [1, [2, [3, [4]], 5]] into [1, 2, 3, 4, 5]
function flatten(list) {
  const out = [];
  for (const item of list) {
    if (Array.isArray(item)) out.push(...flatten(item));   // nested: recurse
    else out.push(item);
  }
  return out;
}
console.log(flatten([1, [2, [3, [4]], 5]]));

// count every file in a folder tree
const folder = {
  name: "projects",
  files: ["notes.txt"],
  folders: [
    { name: "web", files: ["index.html", "app.js"], folders: [] },
    { name: "games", files: ["snake.js"], folders: [{ name: "assets", files: ["a.png", "b.png"], folders: [] }] },
  ],
};
function countFiles(f) {
  let total = f.files.length;
  for (const sub of f.folders) total += countFiles(sub);
  return total;
}
console.log("files:", countFiles(folder));

(Arrays also have a built-in flat(Infinity), which does the same as flatten.)

Stack overflow

A recursive function without a base case, or one that never reaches it, calls itself until the call stack is full. JavaScript then stops it with a RangeError:

function forever(n) {
  return forever(n + 1);     // no base case
}
try {
  forever(1);
} catch (err) {
  console.log(err.name + ":", err.message);
}

The same happens with a correct function given a huge input, because each call uses stack space: browsers allow roughly ten thousand nested calls. For very deep problems, a loop is safer.

Recursion or a loop?

Anything a recursive function does can also be done with a loop, and the other way round.

function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}
console.log(factorialLoop(5));

Common mistakes

Key points

• A recursive function calls itself on a smaller input.
• Every recursive function needs a base case that stops it, and a recursive case that moves towards it.
• Calls wait on the call stack; answers come back up in reverse order.
• Recursion suits nested data; loops suit simple repetition and very large inputs.
• Memoise recursive functions that recalculate the same values.

Practice

1. Write a recursive countUp(n) that prints 1 to n (hint: recurse first, then print).
2. Write a recursive sumArray(list) that adds the numbers of an array.
3. Write a recursive countDigits(n) that returns how many digits a positive number has.
4. Write a recursive gcd(a, b): if b is 0 the answer is a, otherwise it's gcd(b, a % b).
5. Write a recursive function that finds the deepest nesting level of an array like [1, [2, [3]]] (answer 3).