Recursion

Why this matters

Some problems are naturally described in terms of smaller versions of themselves. A directory contains files and directories. An arithmetic expression contains smaller expressions. To sort a list, sort each half and merge them. A function that calls itself, recursion, lets you write such solutions almost exactly as you would describe them. Recursion is how file-tree walkers, parsers, many sorting algorithms and tree data structures are written. In C it also has a very concrete cost, measured in stack frames, which you now know how to picture.

A function that calls itself

The factorial of n, written n!, is 1 x 2 x ... x n. It can be defined in terms of itself:

  n! = 1               if n <= 1     (base case)
  n! = n x (n - 1)!    otherwise     (recursive case)

That definition translates directly into C:

int factorial(int n)
{
    if (n <= 1)
        return 1;                    /* base case: no further calls */
    return n * factorial(n - 1);     /* recursive case: a smaller problem */
}

printf("5! = %d\n", factorial(5));   /* 5! = 120 */

Every correct recursive function has the same two parts:

1. A base case that is answered directly, without recursion.
2. A recursive case that calls the function on a smaller problem, one step closer to the base case, and uses the result.

If every recursive call moves toward the base case, the recursion ends. If not, it runs until the stack overflows.

What happens on the stack

There is nothing special about a function calling itself. Each call is an ordinary call with its own stack frame and its own n. Here is factorial(3):

 calls going down                          returns coming back up

 factorial(3): n=3, needs factorial(2)  ...   returns 3 * 2 = 6
   factorial(2): n=2, needs factorial(1) ...  returns 2 * 1 = 2
     factorial(1): n=1, base case        ...  returns 1

 stack at the deepest point:
 +-------------------------+
 | main                    |
 +-------------------------+
 | factorial  n=3          |  paused at  return n * factorial(n - 1)
 +-------------------------+
 | factorial  n=2          |  paused at the same line, different n
 +-------------------------+
 | factorial  n=1          |  running: returns 1
 +-------------------------+  <- top

Three frames, three separate variables called n, each waiting for the call above it to return. When factorial(1) returns 1, the frame for n=2 resumes, multiplies, returns 2, and so on back down to main.

On the way down and on the way back up

Where you put work relative to the recursive call decides when it happens:

void countdown(int n)
{
    if (n == 0) {
        printf("liftoff\n");
        return;
    }
    printf("%d\n", n);      /* before the call: on the way down */
    countdown(n - 1);
}

3
2
1
liftoff

Work placed after the recursive call happens as the calls return, in reverse order. That is handy for producing digits most-significant first:

void print_digits(int n)
{
    if (n >= 10)
        print_digits(n / 10);   /* first print everything except the last digit */
    printf("%d ", n % 10);      /* then the last digit */
}

print_digits(1234) prints: 1 2 3 4

A loop with n % 10 would naturally produce 4 3 2 1; the stack of pending calls reverses it for free.

Thinking recursively

The trick to writing recursive functions is to trust the recursive call. Do not trace every level in your head. Instead:

1. Find the base case(s): the smallest inputs you can answer immediately.
2. Assume the function already works for smaller inputs.
3. Ask: given the answer for a smaller input, how do I build the answer for this one?

For the digit sum of 4096: assume sum_digits(409) correctly returns 13. Then the answer is 6 + 13. In code: n % 10 + sum_digits(n / 10), with base case sum_digits(0) == 0. Done.

The same reasoning solves the Towers of Hanoi in the exercises, a puzzle that is hard to solve with loops but takes four lines recursively.

The cost: exponential blowup

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, ...) are defined as fib(n) = fib(n-1) + fib(n-2). The direct recursive version is beautiful and terribly slow:

long fib(int n)
{
    if (n < 2)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Each call makes two more calls, and the same values are recomputed over and over: fib(5) computes fib(3) twice and fib(2) three times. Counting the calls:

fib(5) = 5, 15 calls
fib(10) = 55, 177 calls
fib(20) = 6765, 21891 calls
fib(30) = 832040, 2692537 calls
fib(40) = 102334155, 331160281 calls

Three hundred million calls for a number a loop computes in 40 steps:

long fib_loop(int n)
{
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

The lesson is not "recursion is slow" (factorial makes exactly n calls) but "count the calls". When a recursive function calls itself more than once on overlapping subproblems, the cost can explode.

Recursion or a loop?

Anything written recursively can be written with loops (and an explicit stack if necessary), and the reverse is also true. In C:

• Prefer loops for simple linear repetition (sums, factorial, walking a list): no frame per step, no risk of stack overflow on large inputs.
• Prefer recursion for naturally branching structures: trees, nested data, divide-and-conquer algorithms such as quicksort and merge sort, where the depth is only about log n.
• Mind the depth. Each level costs a frame. Recursion one million levels deep will overflow an 8 MB stack. A recursive function that processes untrusted input (like a parser handling deeply nested brackets) should limit its depth.

Some compilers turn a call in tail position (return f(n - 1, acc);, with nothing left to do afterwards) into a jump, using no extra stack. gcc does this at -O2, but the C standard does not require it, so do not rely on it.

Common mistakes

• Missing or unreachable base case. factorial(-1) with a base case of n == 1 never stops: -1, -2, -3, ... until the stack overflows and the program dies with a segmentation fault (exit status 139). Use n <= 1, or reject bad input first.
• Not getting smaller. return n * factorial(n); calls itself with the same argument forever. gcc may warn infinite recursion detected [-Winfinite-recursion].
• Forgetting to use the result. Writing factorial(n - 1); on its own line and then return n; throws the recursive answer away.
• Forgetting return before the recursive call in a non-void function: n * factorial(n - 1); without return falls off the end. Read the -Wreturn-type warning.
• Exponential recursion on overlapping subproblems, as with naive fib. Count the calls.

Recap

• A recursive function calls itself on a smaller problem; it needs a base case and a recursive case that always moves toward it.
• Each call has its own frame and its own copies of parameters and locals.
• Work before the recursive call happens on the way down; work after it happens on the way back up, in reverse order.
• Trust the recursive call: assume it works for smaller inputs and build on it.
• Watch the cost (multiple calls can explode exponentially) and the depth (each level uses stack).

Going further: add a call counter to the naive fib and to fib_loop and compare for n = 35. Then write a recursive int power(int base, int exp) that uses power(base, exp / 2) once and squares it: it needs only about log2(exp) calls.