Recursion

Objectives

By the end of this chapter, you should be able to:

• Explain what a recursive function is
• Identify the base case in a recursive function and explain why it’s required
• Trace a recursive function call by hand, step by step, including how it “unwinds”

💡 Why this matters: Recursion is a different way of thinking about repetition than the loops you already know. Some problems, especially ones with a naturally nested or step-by-step shape, are far cleaner to write recursively. It’s also a common topic in technical interviews, so it’s worth understanding solidly now.

What Is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem, until the problem becomes small enough to answer directly without calling itself again.

That final, directly-answerable version is called the base case. Every recursive function needs one. Without a base case, the function would call itself forever (in practice, JavaScript stops it with an error after too many calls, more on that below).

A First Example: Factorial

The factorial of a number n (written n!) is n * (n - 1) * (n - 2) * ... * 1. For example, 4! = 4 * 3 * 2 * 1 = 24.

Factorial has a natural recursive definition: factorial(n) is n * factorial(n - 1), and the base case is factorial(0), which is defined to be 1.

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(4));
// 24

n === 0 is the base case: when we reach it, the function returns 1 directly, with no further recursive call. Every other call multiplies n by the result of factorial(n - 1), a smaller version of the same problem.

Tracing the Calls

The final answer, 24, doesn’t show what actually happened. Let’s add logging so you can see every call and every return, in order:

function factorialTraced(n) {
  console.log("call factorialTraced(" + n + ")");
  if (n === 0) {
    console.log("base case reached, returning 1");
    return 1;
  }
  const result = n * factorialTraced(n - 1);
  console.log("factorialTraced(" + n + ") returns " + result);
  return result;
}

console.log(factorialTraced(3));
// call factorialTraced(3)
// call factorialTraced(2)
// call factorialTraced(1)
// call factorialTraced(0)
// base case reached, returning 1
// factorialTraced(1) returns 1
// factorialTraced(2) returns 2
// factorialTraced(3) returns 6
// 6

Read that output as two phases:

Phase 1, calling down: factorialTraced(3) calls factorialTraced(2), which calls factorialTraced(1), which calls factorialTraced(0). Each call pauses at the line n * factorialTraced(n - 1), waiting on the call it just made, until the base case finally returns without calling anything further.

Phase 2, unwinding back up: Once factorialTraced(0) returns 1, that answer flows back to the paused factorialTraced(1), which finishes computing 1 * 1 = 1 and returns it. That flows back to factorialTraced(2), which computes 2 * 1 = 2. That flows back to factorialTraced(3), which computes 3 * 2 = 6. This “unwinding” is why the returns lines print in the reverse order of the call lines.

A Second Example: Summing to n

Here’s another classic recursive problem: sum every whole number from 1 up to n.

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

console.log(sumTo(5));
// 15

The base case is n === 1, returning 1 directly. Every other call adds n to the sum of everything smaller than it. Try tracing sumTo(4) by hand before you check the Try It section.

What Happens Without a Base Case

If a recursive function never reaches a case that stops calling itself, JavaScript eventually runs out of room to track all the paused calls and throws an error:

function noBaseCase(n) {
  return noBaseCase(n) + 1;
}

try {
  noBaseCase(1);
} catch (e) {
  console.log(e.name + ": " + e.message);
}
// RangeError: Maximum call stack size exceeded

That error is JavaScript’s way of telling you a recursive function is missing (or never reaching) its base case. Whenever you write a recursive function, write the base case first, and double check that every recursive call is moving toward it.

Try It

1. Trace sumTo(4) by hand, on paper: list each call in order, then list each return value as it unwinds. Then run it and confirm.
2. Write a recursive function countDownFrom(n) that logs each whole number from n down to 1, one per line, then logs "Liftoff!" once it reaches 0 (its base case). Call countDownFrom(4).
3. Write a recursive function power(base, exponent) that returns base raised to exponent, where the base case is exponent === 0 returning 1. Call power(2, 5) and log the result.

Recap

• A recursive function calls itself to solve a smaller version of the same problem.
• Every recursive function needs a base case, the point where it stops calling itself and returns directly.
• Calls happen in two phases: calling down toward the base case, then unwinding back up as each paused call finishes.
• A missing or unreachable base case causes a RangeError: Maximum call stack size exceeded.

Next lesson: higher-order functions, functions that take other functions as arguments or return them.