Recursion

Recursion

A function that calls itself is recursive. It's one of the most elegant (and confusing) ideas in programming.

A function calling itself

int fact(int n) {
  if (n <= 1)   // base case
    return 1;
  return n * fact(n - 1);   // calls itself
}

• The function calls itself with a smaller argument.
• Eventually it hits a base case that stops the recursion.

Anatomy: a base case plus a recursive call

Every recursion needs two parts:

• A base case: the trivial input that returns without recursing. Without it, the function would call itself forever.
• The recursive case: the part where the function calls itself with a smaller input, getting closer to the base.

Tracing factorial

Computing fact(5):

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

Each call waits while the smaller call finishes, then unrolls back up to 5.

Pitfalls

• Missing base case leads to infinite recursion and a stack overflow.
• Not making progress: if the recursive call doesn't shrink the input, it never approaches the base case.
• Each recursive call uses stack memory, so deep chains can exhaust the stack.

TL;DR

• A recursive function is one that calls itself.
• Two parts: base case (stop) plus recursive case (call smaller).
• Factorial example: fact(n) = n * fact(n-1), with a base returning 1.
• Without a base case, recursion runs forever and crashes.