Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Done right, it turns complex problems into elegant, readable solutions. Done wrong, it causes stack overflows and exponential slowdowns. The key is understanding why it works and how to control it.

The Two Required Pieces

Every correct recursive function has exactly two things:

1. Base case — the condition where the function stops and returns a value directly, without calling itself again.
2. Recursive case — the step where the function calls itself with a smaller or simpler input, moving toward the base case.

If you’re missing the base case, you get infinite recursion. If your recursive case doesn’t actually shrink the problem, you get infinite recursion. Both crash with a stack overflow.

Factorial Example

The factorial of n (written n!) is n × (n−1) × (n−2) × … × 1. By definition, 0! = 1.

function factorial(n: number): number {
  // Base case
  if (n <= 1) return 1;
  // Recursive case: n! = n × (n-1)!
  return n * factorial(n - 1);
}

// factorial(4) calls:
//   4 * factorial(3)
//     3 * factorial(2)
//       2 * factorial(1)
//         1   ← base case
//       2 * 1 = 2
//     3 * 2 = 6
//   4 * 6 = 24

Fibonacci and the Problem with Naive Recursion

The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2).

// Naive — O(2^n) time due to redundant calls
function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

This is correct but catastrophically slow. fib(40) makes over a billion recursive calls because it recomputes the same subproblems repeatedly.

Memoization: Caching Recursive Results

Memoization stores the result of each call so we never compute the same value twice.

function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
// Now O(n) time and O(n) space — each value computed exactly once

The Call Stack

Each function call pushes a stack frame onto the call stack, which holds that call’s local variables and return address. When the function returns, the frame is popped. Recursion builds a chain of frames that unwind once the base case is reached.

Call stack for factorial(3):
┌─────────────────┐  ← top (most recent)
│ factorial(1)    │
├─────────────────┤
│ factorial(2)    │
├─────────────────┤
│ factorial(3)    │
└─────────────────┘  ← bottom (first call)

Tail Recursion

A function is tail recursive when the recursive call is the very last operation — no work happens after it returns. Some languages and runtimes optimize tail calls to avoid growing the stack. JavaScript does not reliably perform this optimization, so in JS/TS, prefer iteration for large inputs even when the recursive form is elegant.

Further Learning

Search these terms to go deeper:

• “Recursion CS50 lecture David Malan” — intuitive visual explanation with live tracing
• “The Recurse Book by Eric Roberts” — gentle introduction focused on problem-solving patterns
• “Tail call optimization JavaScript MDN” — details on what JS actually optimizes (and what it doesn’t)
• “Recursion practice problems leetcode easy” — hands-on problems to build pattern recognition

Recursion

Recursion is when a function calls itself to solve a smaller piece of the same problem. Picture Russian nesting dolls: to open the biggest, you open the next, and the next — until you reach the tiny solid one that doesn’t open. That tiny doll is the key to not looping forever.

Every recursion needs two parts

1. Base case — the “stop here” condition that returns an answer without calling itself again (the solid doll).
2. Recursive case — calls itself with a smaller input, heading toward the base case.

Forget the base case (or fail to shrink the problem) and it calls itself forever — which crashes with a “stack overflow.”

A worked example: factorial

4! means 4 × 3 × 2 × 1. Notice 4! = 4 × 3! — the problem contains a smaller version of itself:

function factorial(n) {
  if (n <= 1) return 1        // base case: stop
  return n * factorial(n - 1) // recursive case: smaller problem
}

Tracing factorial(4):

4 * factorial(3)
    3 * factorial(2)
        2 * factorial(1)
            1          ← base case reached
        = 2
    = 6
= 24

Each call waits for the smaller one to finish, then they resolve back up.

The classic trap: repeated work

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8...) written naively is correct but painfully slow:

function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)  // recomputes the same values over and over
}

fib(40) makes over a billion calls because it keeps recalculating the same numbers.

The fix: remember answers (memoization)

Store each result the first time you compute it, then reuse it:

function fib(n, memo = new Map()) {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)  // already known? reuse it
  const result = fib(n - 1, memo) + fib(n - 2, memo)
  memo.set(n, result)
  return result
}

This turns a hopeless calculation into an instant one — you never solve the same subproblem twice.

When to reach for recursion

Recursion shines on things shaped like trees: folders inside folders, the page’s HTML tree, nested menus. For simple “go through a big list” work, a plain loop is usually clearer and safer.

In one sentence

Recursion solves a problem by calling itself on a smaller version until it hits a base case — great for tree-shaped data, but add memoization (a cache) when the same subproblems repeat.

Want to go deeper?

Switch to Expert mode above for the call-stack mechanics, tail recursion, and why JavaScript prefers loops for very large inputs.