Recursion

What you'll learn

How recursion works, why every recursive function needs a base case, how to read the call stack, and when recursion beats a loop.

Why it matters

Trees, graphs, folders and many algorithms (merge sort, backtracking) are naturally recursive. Once you can think recursively, problems that look hard become a few lines of code.

Explanation

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem.

Every recursive function has two parts:

1. Base case: the simplest version, answered directly. It stops the recursion.
2. Recursive case: break the problem down and call the function on a smaller input.

Each call is placed on the call stack (just like the stack you learned about). A call waits until the call it made returns. If there is no base case, calls pile up until the program crashes with a stack overflow.

Complexity: factorial(n) makes n calls, so O(n) time and O(n) stack space. Some recursion, like the naive Fibonacci, repeats work and is O(2 to the n). Dynamic programming (next lessons) fixes that.

Example

Step-by-step walkthrough

1. factorial(5) becomes 5 * factorial(4), which becomes 5 * 4 * factorial(3), and so on until factorial(1) returns 1. Then the answers multiply back: 5 times 4 times 3 times 2 times 1 equals 120.
2. sumTo(4) is 4 + 3 + 2 + 1 + 0, which is 10.
3. countDown(3) prints 3, 2, 1, and then the base case prints Liftoff!.
4. fib(10) adds the two previous Fibonacci numbers each time and returns 55. It works, but it recomputes the same values over and over.

Try it yourself

Write power(base, exp) recursively. The base case is exp === 0, which returns 1.

RecursionJavaScript

Editable codefunction factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1); } function sumTo(n) { if (n === 0) return 0; return n + sumTo(n - 1); } console.log(factorial(5)); console.log(sumTo(4));

Run ResetCopyCtrl+Enter to run

Common mistakes

• No base case, causing a stack overflow.
• A recursive call that does not get closer to the base case.
• Forgetting to return the recursive result.
• Using plain recursion for Fibonacci-style problems, which repeats work.

Quick quiz

Summary

• A recursive function has a base case and a recursive case on a smaller input.
• Each call sits on the call stack until it returns.
• Naive recursion can repeat work; dynamic programming avoids that.

Next: graphs.

function factorial(n) {
  if (n <= 1) return 1;          // base case
  return n * factorial(n - 1);   // recursive case
}

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

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

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

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

console.log(factorial(5));
console.log(sumTo(4));
countDown(3);
console.log(fib(10));