Recursion

Functions that call themselves

Recursion means a function calls itself. It does this to solve a smaller version of the same problem.

That can sound like going round in circles. It isn't, because each call gets a smaller job. In the end, the job is so small that the function can answer it straight away.

A recursive function always has two parts:

• The base case is the smallest input. The function answers it directly, without calling itself.
• The recursive case is every bigger input. The function calls itself with a smaller input, then uses that answer. That call is a recursive call.

You need both parts. Without a base case, the function never stops calling itself. Without a recursive case, it can only answer the smallest input.

This lesson stays at beginner level. It uses small numbers and a small folder tree, so you can see every call. Later lessons go deeper into the same ideas: The call stack, Stack limits & stack overflow, Tail calls, and Advanced recursion.

Start with a countdown. countDown(n) counts from n down to 0. When it reaches 0, it answers "Go!".

function countDown(n) {
  if (n === 0) {
    return "Go!";
  }
  return countDown(n - 1);
}

console.log(countDown(3));
console.log(countDown(0));

Line by line:

• Lines 2 to 4 are the base case. When n is 0, the function returns "Go!". It makes no new call.
• Line 5 is the recursive case. For any other number, the function calls itself with n - 1, a number one smaller. It returns whatever that call returns.
• Line 8 starts at 3. The calls go 3, 2, 1, then 0. At 0, the base case answers "Go!".
• Line 9 starts at 0, so the base case answers straight away.

Both lines print Go!. Line 9 shows a good habit: test the base case on its own first.

Next is factorial. In math, 4! (say "4 factorial") means 4 × 3 × 2 × 1, which is 24. As a function, factorial(4) asks for factorial(3), then multiplies that answer by 4.

Look at the two key parts before you step through the code:

• Lines 2 to 4 are the base case. When n is 1, the function returns 1 right away. The calls stop here.
• Line 5, return n * factorial(n - 1);, is the recursive case. It calls the same function with a number one smaller. When that answer comes back, it multiplies it by n.

1function factorial(n) {2  if (n === 1) {3    return 1;4  }5  return n * factorial(n - 1);6}7 8const answer = factorial(4);Run9console.log(answer);

Notice the order. JavaScript can't finish 4 * factorial(3) until factorial(3) returns. And factorial(3) can't finish until factorial(2) returns, and so on. The base case gives the first finished answer. Every waiting call builds on it.

Every function call needs to remember a few things:

• its parameters, like n;
• its own variables;
• where to carry on when a call it made comes back.

JavaScript keeps this in a list called the call stack. Each call gets one entry on it, called a stack frame.

• A new call puts its frame on top of the stack.
• When that call returns, its frame comes off the top.
• Then the call underneath carries on from where it stopped.

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

console.log(buildNumber(3));

buildNumber(3) calls buildNumber(2) and waits. That calls buildNumber(1) and waits. That calls buildNumber(0), the base case. It returns an empty string, "".

Now the waiting calls finish, newest first. Adding a number to a string joins them as text:

• buildNumber(1) adds 1 to the empty string and returns "1".
• buildNumber(2) adds 2 and returns "12".
• buildNumber(3) adds 3 and returns "123".

So the output is 123. Code written after a recursive call runs on the way back, once the smaller call has returned.

The next player records a real run of fib(4). fib finds Fibonacci numbers. In that list of numbers, each one is the sum of the two before it: 0, 1, 1, 2, 3, 5, and so on. fib(n) gives the number at position n, counting from 0. So fib(4) is 3.

Line 3 calls fib twice. So fib(4) asks for fib(3) and fib(2), and each of those asks for smaller ones again. Some of the same questions get asked more than once. A later lesson shows memoization: saving each answer so you don't work it out again.

1function fib(n) {2  if (n <= 1) return n;3  return fib(n - 1) + fib(n - 2);4}5 6const answer = fib(4);

What if a function calls itself and never reaches a base case? Each call adds one more frame to the call stack, so the stack keeps growing. It can't grow forever. At some point JavaScript stops and throws an error. This is called a stack overflow.

Chrome, Edge, and Node.js show this error as RangeError: Maximum call stack size exceeded. They all use V8, the engine that runs JavaScript inside them. Other browsers can word it differently. Firefox, for example, says "too much recursion".

Click the button below to run a tiny function with no base case. It runs inside try/catch:

• try runs some code.
• catch catches the error if one is thrown, so the page keeps working.

The result shows about how many calls your browser made before it stopped. That number depends on the browser and its settings.

1let depth = 0;2function noBaseCase() {3  depth = depth + 1;4  return noBaseCase();5}6 7try {8  noBaseCase();9} catch (error) {10  console.log(error.name);11  console.log(depth > 0);12}

The fix is not a bigger limit. Instead:

• make sure every recursive call moves closer to the base case, or
• use a loop when a very large number of calls could be waiting at once.

Recursion and loops can solve many of the same problems. You met loops in the Loops: while & for lesson. Here is how the two differ:

• A loop repeats work inside one function call. It changes a counter each time round.
• Recursion repeats work by making a new function call each time.

Both work, but they cost different amounts. The playground below gets the same sum both ways.

1function sumToRecursive(n) {2  if (n === 0) return 0;3  return n + sumToRecursive(n - 1);4}5 6function sumToLoop(n) {7  let total = 0;8  for (let current = n; current > 0; current = current - 1) {9    total = total + current;10  }11  return total;12}

function totalPrices(prices) {
  if (prices.length === 0) return 0;
  const [price, ...rest] = prices;
  return price + totalPrices(rest);
}

console.log(totalPrices([2, 3, 4]));
console.log(totalPrices([]));

Line by line:

• Line 2 is the base case. An empty list adds up to 0.
• Line 3 takes the list apart. This is called destructuring. price gets the first item. ...rest gets all the other items, as a new list.
• Line 4 adds the first price to the total of the rest. That total comes from calling totalPrices again with the shorter list.

It prints 9 for three prices and 0 for an empty list. It works. But this is a flat list: it has no lists inside it. For a flat list, a loop or the array method reduce is usually easier to read.

The table compares the two tools. Read each row as a question, then the answer for recursion and the answer for a loop.

A good rule for now: if the data is flat, try a loop first. If the data has smaller copies of itself inside, recursion can read just like the problem. The Tail calls lesson explains why you shouldn't count on engines saving stack space.

Recursion works best when the data has the same shape inside itself. For example:

• A folder can hold files and more folders.
• A comment can have replies, and each reply can have replies.
• A menu item can have sub-items, and each sub-item can have its own.

Data shaped like this is called a tree. Each item in the tree is called a node.

The examples below use objects and arrays. Stage 3 has full lessons on both. For now, read them like this:

• An object, written in { }, holds named values, like text and replies.
• An array, written in [ ], is a list. .length is how many items it has.

const comment = {
  text: "Useful tip",
  replies: [
    { text: "Thanks", replies: [] },
    { text: "Me too", replies: [{ text: "Same", replies: [] }] },
  ],
};

function countReplies(item) {
  if (item.replies.length === 0) return 0;
  let total = item.replies.length;
  for (const reply of item.replies) {
    total = total + countReplies(reply);
  }
  return total;
}

console.log(countReplies(comment));

Line by line:

• Lines 1 to 7 make a comment with two replies. The second reply has one reply of its own.
• Line 10 is the base case. An item with no replies returns 0.
• Line 11 starts total at the number of direct replies.
• Lines 12 to 14 visit each reply with a for...of loop. For each reply, the function calls itself and adds that reply's count.
• Line 15 returns the total.

The example prints 3: two direct replies, plus one reply inside the second one.

The player below walks through a folder tree in the same way. In its code, a folder has a children list. A file has a size and no children. The function countFiles only needs to handle one node:

• A file has no children, so it counts as 1. This is the base case. !node.children is true when there is no children list.
• A folder asks countFiles about each child and adds up the answers. This is the recursive case.

1const tree = {2  name: "site",3  children: [4    { name: "index.html", size: 4 },5    {6      name: "assets",7      children: [8        { name: "logo.svg", size: 2 },9        { name: "app.js", size: 6 },10      ],11    },12    { name: "notes.txt", size: 1 },13  ],14};15 16function countFiles(node) {17  if (!node.children) return 1;18  let total = 0;19  for (const child of node.children) {20    total = total + countFiles(child);21  }22  return total;23}24 25const answer = countFiles(tree);Run26console.log(answer);

This is the real strength of recursion. The function doesn't need to know how deep the tree goes. The same code works for the top folder, for a folder inside it, and for a folder many levels down. Each call handles its own node and lets the same function handle the children.

Where you'll use this

You won't need recursion for most beginner tasks. But you will meet it in real front-end work whenever data sits inside data. For example:

• Showing a navigation menu where items can have sub-menus.
• Counting or searching the files in a project's folders.
• Showing comments with replies inside replies.
• Flattening a nested array: turning lists inside lists into one list.
• Splitting a problem in half again and again, as in binary search. You'll meet this when you learn algorithms later.

Common misconceptions

Work out the values on paper before you check the answer. For the writing tasks, paste your code into the browser console or an editor. Then add a few tests of your own.

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(5));

function sumTo(n) {
  // your base case and recursive case here
}
console.log(sumTo(5));

function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1);
}
console.log(sumTo(5));

function countDown(n) {
  return countDown(n - 1);
}
console.log(countDown(3));

function countDown(n) {
  if (n === 0) return "done";
  return countDown(n - 1);
}
console.log(countDown(3));

const tree = {
  name: "site",
  children: [
    { name: "index.html", size: 4 },
    { name: "assets", children: [
      { name: "logo.svg", size: 2 },
      { name: "app.js", size: 6 },
    ] },
    { name: "notes.txt", size: 1 },
  ],
};

function countFiles(node) {
  // return 1 for a file; otherwise count every child
}
console.log(countFiles(tree));

const tree = {
  name: "site",
  children: [
    { name: "index.html", size: 4 },
    {
      name: "assets",
      children: [
        { name: "logo.svg", size: 2 },
        { name: "app.js", size: 6 },
      ],
    },
    { name: "notes.txt", size: 1 },
  ],
};

function countFiles(node) {
  if (!node.children) return 1;
  let total = 0;
  for (const child of node.children) {
    total = total + countFiles(child);
  }
  return total;
}
console.log(countFiles(tree));

let n = 3;
const steps = [];
while (n > 0) {
  steps.push(n);
  n = n - 1;
}
steps.push("Go!");
console.log(steps.join(", "));

Every answer explains why it is right or wrong. If a code question feels hard, find the base case first. Then write out the recursive case one step at a time on paper.

Key takeaways

• Recursion means a function calls itself to solve a smaller version of the same problem.
• Every recursive function needs a base case it can reach, and a recursive case that moves closer to it.
• The call stack grows while calls wait. It shrinks as each call returns.
• If the base case is missing or never reached, the stack fills up and JavaScript throws a RangeError.
• For simple repeats, a loop is usually better. For trees and other data inside data, recursion is often clearer.

Coming next: Object basics, where you learn the objects used in this lesson's tree examples.