Recursion

"To understand recursion, you must first understand recursion — but seriously, it's just a function that calls itself to solve a smaller version of the same problem."

Part 1: The Two Rules of Recursion

Every recursive function must have exactly two things. Miss either one and your program will crash with a stack overflow.

1. Base Case (the stop condition)

The condition that ends the recursion. Without it, the function calls itself forever. This is the most important part.

2. Recursive Case (the reduction)

The part where the function calls itself with a smaller input — moving closer to the base case each time.

The simplest example: countdown

javascript

function countdown(n) {
    if (n <= 0) {        // Base case — stop here
        console.log("Done!");
        return;
    }
    console.log(n);     // Do some work
    countdown(n - 1);  // Recursive case — smaller problem
}

countdown(5);
// Output: 5 4 3 2 1 Done!

Part 2: Classic Examples

Factorial — n!

5! = 5 × 4 × 3 × 2 × 1 = 120. The key insight: factorial(5) = 5 × factorial(4). Every step is the same problem but one size smaller.

javascript

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

console.log(factorial(5));  // 120
console.log(factorial(1));  // 1
console.log(factorial(0));  // 1

// How it resolves:
// factorial(5)
//   5 * factorial(4)
//         4 * factorial(3)
//               3 * factorial(2)
//                     2 * factorial(1)
//                               1
// = 5 * 4 * 3 * 2 * 1 = 120

Fibonacci

Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13… This is a classic recursion example — but watch out, the naive version is slow (O(2ⁿ)).

javascript

function fib(n) {
    if (n <= 1) return n;               // Base cases: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);   // Recursive case
}

console.log(fib(6));  // 8
console.log(fib(0));  // 0
console.log(fib(1));  // 1

// fib(6) = fib(5) + fib(4) = 5 + 3 = 8

Sum of digits

javascript

function sumDigits(n) {
    if (n < 10) return n;                      // Single digit — base case
    return (n % 10) + sumDigits(Math.floor(n / 10));
}

console.log(sumDigits(1234)); // 10 (1+2+3+4)
console.log(sumDigits(99));   // 18 (9+9)

Part 3: The Call Stack

Every time a function is called, JavaScript pushes a frame onto the call stack. When it returns, that frame is popped off. With recursion, many frames stack up before any of them resolve.

Visualizing the call stack for factorial(3)

javascript

// factorial(3) is called
//   → pushes factorial(3) onto stack
//   → calls factorial(2)
//     → pushes factorial(2) onto stack
//     → calls factorial(1)
//       → pushes factorial(1) onto stack
//       → returns 1  ← stack unwinds
//     ← factorial(2) returns 2 * 1 = 2
//   ← factorial(3) returns 3 * 2 = 6

console.log(factorial(3)); // 6

Stack Overflow — too many recursive calls

If the base case is missing or never reached, the call stack grows until JavaScript throws a RangeError: Maximum call stack size exceeded.

javascript

// ❌ No base case — infinite recursion
function broken(n) {
    return broken(n - 1); // Never stops!
}
// RangeError: Maximum call stack size exceeded

// ✅ Always have a base case that is reachable
function fixed(n) {
    if (n <= 0) return 0;
    return fixed(n - 1);
}

Recursion vs Iteration — when to use which?

javascript

// Both compute the same thing:

// Iterative factorial
function factIter(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) result *= i;
    return result;
}

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

// Use recursion when the problem is naturally tree-shaped
// (e.g., file systems, binary trees, subsets).
// Use iteration for simple linear repetition — it's faster.