Recursion and How It Uses the Stack

Part I · Module 5 · Chapter 5.8 · Recursion and How It Uses the Stack

1. A Function That Calls Itself

Some problems are naturally described in terms of a smaller version of themselves. The factorial of 4 is 4 times the factorial of 3; the factorial of 1 is 1. That second sentence is what stops the description going on forever.

Written directly:

#include <stdio.h>

unsigned int factorial(unsigned int n)
{
    printf("  factorial(%u) begins\n", n);

    if (n <= 1u) {
        printf("  factorial(%u) is the base case, returning 1\n", n);
        return 1u;
    }

    unsigned int smaller = factorial(n - 1u);
    unsigned int result = n * smaller;
    printf("  factorial(%u) returns %u * %u = %u\n", n, n, smaller, result);

    return result;
}

int main(void)
{
    printf("answer %u\n", factorial(4u));

    return 0;
}

Output:

  factorial(4) begins
  factorial(3) begins
  factorial(2) begins
  factorial(1) begins
  factorial(1) is the base case, returning 1
  factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
  factorial(4) returns 4 * 6 = 24
answer 24

Compare that trace with Chapter 5.7 §2's. It is the same shape — four calls going in, four returns coming out in reverse order — and the only difference is that all four frames belong to the same function.

Two things are worth taking from it.

Four objects called n exist at once, holding 4, 3, 2 and 1. Chapter 5.7 explained why: four frames, four sets of locals. Nothing new is needed to understand this.

The answer is assembled on the way back. Going in, nothing is computed — each call suspends and waits. The first actual multiplication happens after the base case returns, and the result is built up as the frames unwind. A recursive function that does its work on the way out, like this one, is doing genuinely different work from one that does it on the way in.

2. The Two Obligations

Chapter 4.4 said a loop is three obligations: initialise, test, change. Recursion is the same idea with two:

A base case — at least one path that returns without calling itself. Progress — every recursive call must move the arguments toward that base case.

factorial has both. The base case is n <= 1u. The progress is n - 1u, which strictly decreases and therefore must reach 1.

That should sound familiar. Chapter 4.4 asked you to name the quantity that strictly decreases and explain why it cannot decrease forever. Recursion needs exactly the same argument. It is not a different obligation reached by a different route; it is the same termination argument, with the frame depth standing in for the loop count.

Before writing a recursive function, state its termination argument out loud: what gets smaller, and what stops it.

3. What the Compiler Will and Will Not Catch

This is worth knowing precisely, because the answer is encouraging for one failure and not for the other.

No base case at all

unsigned int countdown(unsigned int n)
{
    return countdown(n - 1u);
}

warning: all paths through this function will call itself
    [-Winfinite-recursion]

Good news: -Winfinite-recursion is part of -Wall, so you get this one by default. After the three previous chapters that each needed an extra flag, that is a pleasant change.

A base case that is never reached

unsigned int shrink(unsigned int n)
{
    if (n == 0u) {
        return 0u;
    }

    return shrink(n);        /* n never changes */
}

Built with -Wall -Wextra -Wpedantic -Winfinite-recursion:

(no diagnostics)

Silent. Not one warning. There is a path that returns without recursing, so the diagnostic's condition — all paths call the function — is not met. The compiler has no way to know that the path is unreachable.

4. What It Costs

Each level of recursion is a call, and Chapter 5.7 established what a call costs: a frame, holding that level's parameters, locals and resume point, which lives until that level returns.

For factorial(4) that is four frames. The depth is small and the cost is irrelevant. The question is what happens when the depth is not small.

Recursion depth is the number of frames alive at once. Before writing a recursive function, ask what the deepest call chain is as a function of the input, and whether that number is bounded by something you control.

Three shapes, in order of how worried to be:

The third row is the dangerous one, and it is the one most teaching examples fall into. factorial(n) uses n frames; a caller passing a large n chooses how much of the frame region to consume. The region is finite, C does not say how large it is, and C does not define what happens when it runs out. On a hosted system the program is usually terminated; on an embedded target without that protection the consequences can be worse.

The other limit

Depth is not the only thing to check:

#include <stdio.h>

unsigned int factorial(unsigned int n)
{
    if (n <= 1u) {
        return 1u;
    }

    return n * factorial(n - 1u);
}

int main(void)
{
    for (unsigned int k = 10u; k <= 14u; k++) {
        printf("%2u! = %u\n", k, factorial(k));
    }

    return 0;
}

Output:

10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280

13! is 6227020800. The program printed 1932053504.

Nothing went wrong with the recursion. unsigned int on this implementation cannot hold 6227020800, and Chapter 2.6 established that unsigned arithmetic wraps rather than overflowing — defined behaviour, producing a wrong answer with no warning and no symptom. The recursion was never the limiting factor; the type was.

That is the general lesson, and it is worth more than the factorial: a correct algorithm in a type too small for its results is a wrong program. Choosing the return type is part of writing the function.

5. When Recursion Is Actually the Better Choice

Factorial is a bad advertisement for recursion. Here it is as a loop:

unsigned int factorial(unsigned int n)
{
    unsigned int result = 1u;

    for (unsigned int k = 2u; k <= n; k++) {
        result = result * k;
    }

    return result;
}

One frame instead of n, no depth question at all, and arguably easier to read. For a problem whose structure is a simple count, a loop is the right answer. Saying otherwise because recursion looks clever is how the technique gets its reputation for being impractical.

Euclid's algorithm is a fairer test, because its definition is recursive: the greatest common divisor of a and b is the greatest common divisor of b and a mod b, and when b is zero the answer is a.

#include <stdio.h>

unsigned int gcd_recursive(unsigned int a, unsigned int b)
{
    if (b == 0u) {
        return a;
    }

    return gcd_recursive(b, a % b);
}

unsigned int gcd_iterative(unsigned int a, unsigned int b)
{
    while (b != 0u) {
        unsigned int remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main(void)
{
    printf("recursive gcd(1071, 462) = %u\n", gcd_recursive(1071u, 462u));
    printf("iterative gcd(1071, 462) = %u\n", gcd_iterative(1071u, 462u));
    printf("recursive gcd(13, 0)     = %u\n", gcd_recursive(13u, 0u));

    return 0;
}

Output:

recursive gcd(1071, 462) = 21
iterative gcd(1071, 462) = 21
recursive gcd(13, 0)     = 13

Both give 21, agreeing with Chapter 4.4's iterative version. The recursive one is four lines and is a direct transcription of the mathematical definition — there is no temporary, no reassignment of a and b, and nothing to get wrong in the order.

The depth is also safe here, and for a non-obvious reason: each step replaces b with a mod b, which shrinks fast, so the depth grows roughly like the logarithm of the inputs rather than their size. That is the second row of §4's table. Knowing which row your function is in is the judgement the chapter is asking for.

Note too that gcd_recursive(13, 0) returns 13 without recursing at all. A base case that the very first call can satisfy is a good sign — it means the function handles its boundary without a special path.

6. What You Should Be Able to Say Now

1. A recursive call needs no new machinery — it is an ordinary call with its own frame.
2. Several objects with the same name exist at once, one per level — Chapter 5.7's frames.
3. In factorial, the answer is assembled on the way back, as the frames unwind.
4. Recursion has two obligations: a base case, and progress toward it.
5. That is Chapter 4.4's termination argument, with depth in place of iteration count.
6. No base case at all is caught by -Winfinite-recursion, which is in -Wall.
7. A base case that is never reached is silent. The compiler checks the shape, not the argument.
8. Depth is the cost. Judge whether it is bounded, logarithmic, or chosen by the caller.
9. The type can fail before the recursion does — unsigned int factorial is wrong from 13!.
10. Tail call elimination is not guaranteed. If the depth is unbounded, write the loop.

7. Exercises

Exercise 1 — predict the trace. Do not compile yet. Give every line, in order.

#include <stdio.h>

unsigned int down(unsigned int n)
{
    printf("in %u\n", n);
    if (n == 0u) {
        return 0u;
    }
    unsigned int r = down(n - 1u);
    printf("out %u\n", n);
    return r + n;
}

int main(void)
{
    printf("total %u\n", down(3u));
    return 0;
}

Then say how many frames existed at the moment in 0 was printed.

Exercise 2 — state the termination argument. For each, name what strictly decreases and what stops it, or say that nothing does.

f(n)  -> returns 1 if n == 0, else f(n - 1)
g(n)  -> returns 1 if n == 0, else g(n - 2)
h(n)  -> returns 1 if n <= 1, else h(n / 2)
k(n)  -> returns 1 if n == 100, else k(n + 1)

Pay particular attention to g with an odd starting value.

Exercise 3 — predict the diagnostic. For each, say whether -Wall warns, and why.

int a(int n) { return a(n - 1); }
int b(int n) { if (n == 0) return 0; return b(n); }
int c(int n) { if (n == 0) return 0; return c(n - 1); }

Exercise 4 — judge three depths. For each, say which row of §4's table it falls into and whether you would ship it.

• summing the integers from n down to 1 by recursion
• repeatedly halving a range until it has one element
• walking four fixed levels of a configuration hierarchy
• counting down from a value supplied by whoever calls your function

Exercise 5 — find the real limit. §4's factorial is wrong from 13! onward with unsigned int. Say what the first wrong result is, why there is no warning, and two different changes that would push the limit further. Then say what you would do if the required range exceeded every available integer type.

Exercise 6 — convert it. Rewrite Exercise 1's down as a loop. Say how many frames the loop version uses regardless of n, and which version you would ship for an n that a caller chooses.

Exercise 7 — fix the silent one. shrink in §3 has a correct base case and never terminates. Give the smallest repair, then state the termination argument the repaired version has.

Exercise 8 — defend a choice. A reviewer rejects §5's gcd_recursive on the grounds that "recursion is risky." Give a two-sentence reply that uses §4's table, and say what you would need to change about the function for their objection to become correct.

8. Summary

• A recursive call is an ordinary call — Chapter 5.7's frame model already explains all of it.
• Each level has its own parameters and locals; factorial(4) has four n objects alive at once.
• Work can happen on the way in or, as in factorial, on the way back as frames unwind.
• Two obligations: a base case and progress toward it — Chapter 4.4's termination argument again.
• -Winfinite-recursion catches no base case and is in -Wall. It does not catch a base case that is never reached.
• Depth is the cost. Bounded and logarithmic depths are fine; a depth the caller chooses deserves care.
• A correct recursion in too small a type is still a wrong program — 13! proves it.
• Tail call elimination is not a C guarantee. Unbounded depth means write the loop.

Module 5 now has all its mechanics: how to define a function, what a call transfers, what comes back, how names resolve, where the objects live, and what happens when a function calls itself. What none of that settles is which functions should exist. Every program in this module has had its decomposition handed to it, and the decisions behind those choices — what belongs in one function, what a good name promises, and what makes a function easy or impossible to check — have been made silently throughout. The last chapter makes them explicit.