Recursion

Open a folder on your computer and you find files and more folders. Open one of those and you find files and more folders again. To count every file, you do the same job at each level: count the files here, then repeat the job inside each folder. A function that solves a problem by calling itself on a smaller part of the problem is called recursive.

In this lesson you will write recursive functions, watch how JavaScript runs them on the call stack, use them on nested data such as category menus, and learn when a plain loop is the better choice.

A function that calls itself

Every recursive function has two parts:

• A base case: the simplest version of the problem, answered directly with no further calls. This is what stops the recursion.
• A recursive case: the function calls itself with a smaller input, moving one step closer to the base case.

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

countdown(3);

3
2
1
Lift-off!

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), and so on until countdown(0) hits the base case. Without the if, or if n never reached 0 (try calling countdown(2.5)), the calls would never stop.

How the call stack handles recursion

The call stack is the list of functions that are running right now (you met it in How Asynchronous Code Works). Every call gets its own frame on the stack, with its own copy of the parameters and local variables. When a function returns, its frame is removed and the caller continues from where it paused.

This example calculates a factorial (4! means 4 × 3 × 2 × 1) and prints a line each time a frame is added or removed. The extra depth parameter is only there to indent the output.

function factorial(n, depth = 0) {
  const pad = "  ".repeat(depth);
  console.log(`${pad}factorial(${n}) called`);
  if (n <= 1) {
    console.log(`${pad}base case: return 1`);
    return 1;
  }
  const result = n * factorial(n - 1, depth + 1);
  console.log(`${pad}return ${n} * ... = ${result}`);
  return result;
}

console.log("Answer:", factorial(4));

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      base case: return 1
    return 2 * ... = 2
  return 3 * ... = 6
return 4 * ... = 24
Answer: 24

Read the output as two journeys. On the way down, each call waits for the answer to a smaller problem, so four frames pile up. On the way back up, each frame receives an answer, multiplies, and returns. Every n keeps its own value because each frame has its own variables.

Recursion or a loop?

Anything recursion can do, a loop can do too, and the other way round. For simple counting, the loop is clearer and safer:

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

function sumRecursive(n) {
  if (n === 0) return 0;
  return n + sumRecursive(n - 1);
}

console.log(sumLoop(100), sumRecursive(100));
console.log(sumLoop(100000));
try {
  console.log(sumRecursive(100000));
} catch (error) {
  console.log("Recursive version failed:", error.name);
}

5050 5050
5000050000
Recursive version failed: RangeError

Both give 5050 for 100. For 100,000, the recursive version needs 100,000 frames at once and the browser refuses. (Firefox names this error InternalError; Chrome, Edge, Safari and Node use RangeError.)

So when is recursion the better choice? When the data itself is nested and you do not know how deep it goes: menus with sub-menus, folders inside folders, comments with replies, the elements of a web page, or a JSON response with objects inside objects. A loop handles one level well; recursion handles any number of levels with the same few lines.

Recursion on nested data

An online shop in Pune keeps its categories as a tree. Every category has a name and an array of children, which are categories too.

const menu = {
  name: "All products",
  children: [
    {
      name: "Electronics",
      children: [
        { name: "Mobiles", children: [] },
        {
          name: "Laptops",
          children: [
            { name: "Gaming", children: [] },
            { name: "Students", children: [] },
          ],
        },
      ],
    },
    { name: "Books", children: [{ name: "Exam guides", children: [] }] },
  ],
};

function printTree(node, level = 0) {
  console.log("  ".repeat(level) + "- " + node.name);
  for (const child of node.children) {
    printTree(child, level + 1);
  }
}

function countCategories(node) {
  let count = 1; // this node
  for (const child of node.children) {
    count += countCategories(child);
  }
  return count;
}

printTree(menu);
console.log("Total categories:", countCategories(menu));

- All products
  - Electronics
    - Mobiles
    - Laptops
      - Gaming
      - Students
  - Books
    - Exam guides
Total categories: 8

Where is the base case? A category with an empty children array runs the loop zero times, so it makes no further calls. Leaves of the tree end the recursion naturally.

The same pattern works for arrays inside arrays. Here a shopper's boxes contain prices and more boxes:

const cartBoxes = [499, [120, 80], [[1299], 45], []];

function deepSum(items) {
  let total = 0;
  for (const item of items) {
    total += Array.isArray(item) ? deepSum(item) : item;
  }
  return total;
}

console.log(deepSum(cartBoxes));
console.log(cartBoxes.flat(Infinity));

2043
[ 499, 120, 80, 1299, 45 ]

For flattening alone, the built-in flat(Infinity) from Array Methods already does the recursion for you. Write your own when you need to do something at each level.

Advanced: faster and deeper recursion

Remembering answers (memoisation)

Some recursive functions repeat the same work many times. The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8...) defines each number as the sum of the two before it. A direct version calls fib(23) twice, fib(22) three times and so on, about 240,000 calls for fib(25). Storing answers in a Map (see Map & Set) cuts that to a few dozen:

const memo = new Map();

function fib(n) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fib(n - 1) + fib(n - 2);
  memo.set(n, value);
  return value;
}

console.log(fib(50));

12586269025

Very deep data: use your own stack

The call stack has a limit: thousands or tens of thousands of nested calls, depending on the browser and the size of each frame. Real data is rarely that deep, but generated or user-created data can be. You can then replace recursion with a loop that keeps its own array as a stack:

function countWithStack(root) {
  const stack = [root];
  let count = 0;
  while (stack.length > 0) {
    const node = stack.pop();
    count++;
    stack.push(...node.children);
  }
  return count;
}

This visits the same nodes as countCategories, but an array can hold millions of items, so a chain of 50,000 nested categories is no problem. (The language specification describes "proper tail calls" that would avoid stack growth for some recursive calls, but only Safari implements them, so do not rely on them.)

Common mistakes

• No base case, or one that is never reached. Check that every call moves closer to the base case, for example n - 1 with integer n.
• Forgetting to return the recursive result. countCategories(child); without using the value throws the answer away.
• Sharing one variable between calls by accident. Keep counters inside the function, or pass them as parameters, rather than using a global.
• Using recursion for long, flat jobs. Counting to 100,000 needs a loop, not 100,000 stack frames.

Key points

• A recursive function calls itself on a smaller version of the problem.
• Every recursive function needs a base case that stops the calls.
• Each call gets its own stack frame with its own variables; frames return in reverse order.
• Recursion shines on nested data of unknown depth: trees, folders, menus, comments.
• Too many nested calls cause "Maximum call stack size exceeded"; use a loop with your own stack for very deep data.
• Memoisation stores answers so repeated sub-problems are solved only once.

const thread = {
  author: "Isha",
  text: "Maths test moved to Friday",
  replies: [
    {
      author: "Kabir",
      text: "Which chapters?",
      replies: [{ author: "Meera", text: "Chapters 4 to 6", replies: [] }],
    },
    { author: "Rohan", text: "Thanks!", replies: [] },
  ],
};

function countComments(comment) {
  let count = 1;
  for (const reply of comment.replies) count += countComments(reply);
  return count;
}

function authors(comment) {
  return [comment.author, ...comment.replies.flatMap(authors)];
}

console.log(countComments(thread));
console.log(authors(thread));

4
[ 'Isha', 'Kabir', 'Meera', 'Rohan' ]