Recursion: Functions That Call Themselves

Two parts, always

Recursion is a function defined in terms of itself. Every correct recursive function has exactly two parts. The base case is a small input you can answer immediately, with no further calls — it stops the process. The recursive case does a little work, then calls the same function on a smaller input, trusting it to come back with the right answer.

The classic first example is factorial: n! = n × (n−1)!, and 0! = 1. That definition *is* the recursion — the base case is 0, and each step peels off one factor and defers the rest.

long long fact(int n) {
    if (n == 0) return 1;        // base case
    return n * fact(n - 1);      // recursive case: smaller input
}
// fact(4) = 4 * fact(3) = 4 * 3 * fact(2) = ... = 24

The call stack does the bookkeeping

How does the computer remember that fact(4) still owes a `4 *` after fact(3) returns? It uses the call stack — the very same Last-In-First-Out structure you met in the linear-structures rung. Each call pushes a stack frame holding its local variables and where to resume. When a call returns, its frame pops and control hands back to the caller.

Calling fact(3): frames pushed downward, then popped (return).

  push  fact(3)  waits for fact(2)
  push  fact(2)  waits for fact(1)
  push  fact(1)  waits for fact(0)
  push  fact(0) = 1   <-- base case, returns now
        fact(1) = 1*1 = 1   pop
        fact(2) = 2*1 = 2   pop
        fact(3) = 3*2 = 6   pop  --> answer

This is why recursion feels like trust: you write fact(n) *as if* fact(n−1) already works. The stack quietly tracks the half-finished work for you, so you never have to.

When recursion repeats work: Fibonacci

Recursion is elegant but not automatically efficient. The Fibonacci numbers — fib(n) = fib(n−1) + fib(n−2), with fib(0)=0, fib(1)=1 — make two recursive calls each. Drawing the recursion tree shows the same subproblems computed over and over.

fib(5)
           ____________ fib(5) ____________
          /                                \
      fib(4)                              fib(3)
      /     \                            /     \
   fib(3)   fib(2)                    fib(2)   fib(1)
   /   \     /  \                      / \
fib(2) f1  f1  f0                   f1  f0
 / \
f1 f0

  fib(3) is computed twice, fib(2) three times ... work explodes.

The fix is memoization: remember each fib(k) the first time you compute it, then reuse it. That collapses the tree to a line and turns O(2^n) into O(n). You'll meet this idea again, in force, in the dynamic-programming rung.

Two ways recursion goes wrong

Because every call eats a stack frame, recursion has two famous failure modes. Infinite recursion is forgetting the base case (or never moving toward it), so the function calls itself forever. Stack overflow is recursing too deep — even correct recursion crashes if it nests, say, a million frames, because the stack has finite size.

// BUG: no base case is ever reached -> infinite recursion -> stack overflow
int bad(int n) {
    return bad(n - 1);    // never stops; n races past 0 into negatives
}
// FIX: a base case that the recursion actually reaches
int good(int n) {
    if (n <= 0) return 0;
    return good(n - 1);
}