Intro to Recursion

Recursion is one of those topics that feels magical until it clicks — and then it becomes one of the most powerful tools in your kit.

Recursion Explained Visually

Switch to Watch Mode to follow along

The Two Rules of Recursion

Every recursive function needs exactly two things:

1. A base case — the condition that stops the recursion.
2. A recursive step — where the function calls itself with a smaller version of the problem.

Break either rule, and you'll get an infinite loop (or more precisely, a stack overflow).

Classic Example: Factorial

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

factorial(5); // 5 × 4 × 3 × 2 × 1 = 120

Try it yourself — edit n, then press Run to see the result:

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

console.log(factorial(5));

What Happens on the Call Stack?

factorial(5)
  → 5 × factorial(4)
    → 4 × factorial(3)
      → 3 × factorial(2)
        → 2 × factorial(1)
          → 1  ← base case hit, start unwinding
        → 2 × 1 = 2
      → 3 × 2 = 6
    → 4 × 6 = 24
  → 5 × 24 = 120

Each call waits for the one below it to finish before it can compute its result. That "waiting" is the call stack growing.

When to Use Recursion

Recursion shines when the problem has self-similar sub-problems:

• Tree traversal (DOM, file systems, ASTs)
• Divide-and-conquer algorithms (merge sort, quicksort)
• Backtracking (sudoku solvers, path finding)
• Mathematical definitions (Fibonacci, factorials, permutations)

When Not to Use It

If a simple for loop solves the problem clearly, prefer iteration. Recursion adds call-stack overhead and can blow the stack on very deep inputs unless you use tail-call optimization (which JavaScript engines don't reliably support).

Up next: we'll combine recursion with Big-O to analyze merge sort — a beautiful divide-and-conquer algorithm.