Recursion

The problem

You need to multiply 5 × 4 × 3 × 2 × 1 to get 5!. Easy. Now do 100!. You are not going to write a hundred multiplications by hand, and a loop feels like overkill for something you can describe in one breath.

Here is the breath: 5! is just 5 × 4!. And 4! is just 4 × 3!. Every factorial is a slightly smaller factorial waiting to happen. The problem literally contains a smaller copy of itself. Can your code say that as plainly as you just did?

A first attempt

Reach for a loop and you get something that works but hides the idea:

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Nothing is wrong here — it runs in O(n) time and O(1) space. But you had to invent a result accumulator and a counter i that have nothing to do with the definition of a factorial. The loop describes how to grind it out, not what a factorial is. When the structure of a problem is self-similar, a loop forces you to flatten that structure by hand.

The insight

A function is allowed to call itself. If factorial(5) can ask factorial(4) for its answer and just multiply by 5, you never have to manage a counter at all. You describe the problem in terms of a smaller version of the same problem.

Two things make this safe rather than an infinite loop:

• A base case — the smallest input you can answer with no further help. factorial(1) is 1.
• A recursive case — everything else, expressed using a smaller input that marches toward the base case.

That is recursion: a function defined in terms of itself, anchored by a base case.

How it works

factorial(4)
= 4 * factorial(3)
      = 3 * factorial(2)
            = 2 * factorial(1)
                  = 1          <- base case
            = 2 * 1 = 2
      = 3 * 2 = 6
= 4 * 6 = 24

The code

def factorial(n):
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)  # recursive case


print(factorial(5))  # 120

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

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

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

// factorial(5) -> 120

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

/* factorial(5) -> 120 */

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

// factorial(5) -> 120

Complexity

Note the hidden cost: the iterative loop was O(1) space, but recursion pays O(n) for the call stack. Elegance is not free.

When to use it

Practice

Recap

• A recursive function solves a problem by calling itself on a smaller input.
• Every recursion needs a base case to stop and a recursive case that shrinks toward it.
• Recursion trades O(n) stack space for code that mirrors a self-similar problem.