Understanding Recursion

Recursion is when a function calls itself. That's it. The trick is understanding why it works and when to use it.

The Mental Model

Think of recursion as delegation:

"To clean the house, clean this room, then clean the rest of the house."

The function keeps delegating smaller pieces until there's nothing left to delegate (the base case).

The Two Required Parts

Every recursive function needs:

1. Base case: When to stop

2. Recursive case: How to break down the problem

function countdown(n) {

  // Base case: stop at 0
  if (n <= 0) {
    console.log("Done!");
    return;
  }
  // Recursive case: do work, then delegate
  console.log(n);
  countdown(n - 1);
}

Classic Example: Factorial

5! = 5 × 4 × 3 × 2 × 1 = 120

function factorial(n) {

  if (n <= 1) return 1;        // Base case
  return n * factorial(n - 1); // Recursive case
}

How it executes:

factorial(5)

= 5 * factorial(4)
= 5  4  factorial(3)
= 5  4  3 * factorial(2)
= 5  4  3  2  factorial(1)
= 5  4  3  2  1
= 120

When Recursion Makes Sense

Recursion shines for self-similar structures:

- Trees: Each node is a mini-tree

- Nested data: JSON, file systems

- Divide-and-conquer: Mergesort, quicksort

// Traversing a file tree

function listFiles(directory) {
  for (let item of directory.contents) {
    if (item.isFile) {
      console.log(item.name);
    } else {
      listFiles(item); // It's a directory, recurse
    }
  }
}

When NOT to Use Recursion

- Simple counting/iteration (use loops)

- When you might hit stack limits (deep recursion)

- When an iterative solution is clearer

The Stack Limit Problem

Each recursive call adds to the call stack. Too deep = stack overflow.

// This will crash with large n

function badSum(n) {
  if (n <= 0) return 0;
  return n + badSum(n - 1);
}
badSum(100000); // Stack overflow!

For deep recursion, use iteration or tail-call optimization (if your language supports it).

Key Takeaway

Recursion isn't magic—it's a pattern. Ask yourself:

1. What's the smallest version of this problem? (base case)

2. How does solving a smaller piece help solve the whole? (recursive case)

If those answers are clear, recursion might be the right tool.