Recursion

1The two obligations

Every correct recursive function satisfies two conditions. Miss either and it does not terminate.

A base case that returns without recursing. It answers the smallest version of the problem directly.

A recursive case that calls itself on input strictly closer to the base case. "Smaller" must be measurable and must be guaranteed to decrease, or the recursion is infinite.

long factorial(int n)
{
    if (n <= 1) {
        return 1;              /* base case */
    }
    return n * factorial(n - 1);   /* n decreases, so it must reach 1 */
}

Note that the base case is n <= 1 rather than n == 1. Testing for exact equality is the most common way to write an infinite recursion: call factorial(-1) and a function guarded by n == 1 descends forever. Guard the whole range you cannot handle, not the single value you expect.

2What happens on the stack

Week 17 established that each call pushes a frame. Recursion pushes one per level, and they all exist simultaneously until the base case is reached.

That last point is worth dwelling on. Nothing is multiplied on the way down; each frame is suspended holding its own n, waiting for the answer from below. The work happens during unwinding, which is why the memory cost is proportional to the depth.

3Depth and stack overflow

Each frame costs memory: the parameters, the locals, the saved return address, and alignment padding. Call it a few dozen bytes for a simple function, more if it has a large local array.

ulimit -s          # stack limit in kilobytes; typically 8192 on Linux

With 8 MB of stack and roughly 48 bytes per frame, a simple recursion can reach somewhere near 150 000 levels. Add a 1 KB local array to the function and that collapses to about 8 000.

There is no graceful failure. The stack grows into a guard page and the program receives a fatal signal — no NULL to check, no error to catch. Sanitizers report it clearly:

gcc -fsanitize=address …
==1234==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc...

Practical consequence: recursion depth must be bounded by something you control. Recursing over a balanced tree of a million nodes is fine — depth about 20. Recursing once per element of a million-element list is not.

Tail calls

A tail call is a recursive call whose result is returned directly, with nothing left to do afterwards:

/* not a tail call: the multiplication happens after the call returns */
return n * factorial(n - 1);

/* tail call: nothing remains after the call */
return factorial_helper(n - 1, accumulator * n);

A compiler may turn a tail call into a jump, reusing the current frame instead of pushing a new one — which makes the recursion run in constant stack space. GCC and Clang do this at -O2. But the C standard does not require it, so you cannot rely on it for correctness. Treat it as an optimization you may benefit from, never as a guarantee.

4When recursion is the right shape

The pattern: use recursion when the data or the definition is recursive, and the depth is logarithmic or otherwise bounded. Use iteration for linear sequences.

The Fibonacci trap

long fib(int n)
{
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);      /* two calls per level */
}

This is the textbook example of recursion and a genuinely terrible program. Each call spawns two more, so the work grows exponentially: fib(40) makes over 300 million calls and takes seconds. fib(50) would take minutes.

The problem is not recursion but repeated recursion — fib(35) is computed millions of times. Two fixes:

/* memoize: remember what you already computed */
long fib_memo(int n, long cache[])
{
    if (n <= 1)        return n;
    if (cache[n] != 0) return cache[n];
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
    return cache[n];
}

/* or simply iterate: O(n) time, O(1) space */
long fib_iter(int n)
{
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

Both are linear. The iterative version is the one to ship.

5Worked example: Hanoi, search, and the stack under a debugger

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static long call_counter = 0;

/* --- factorial, to watch frames unwind --- */
static long factorial(int n, int depth)
{
    printf("%*scall  factorial(%d)\n", depth * 2, "", n);
    long result;
    if (n <= 1) {
        result = 1;
    } else {
        result = n * factorial(n - 1, depth + 1);
    }
    printf("%*sreturn %ld\n", depth * 2, "", result);
    return result;
}

/* --- Towers of Hanoi: the definition is itself recursive --- */
static void hanoi(int disks, char from, char to, char via, int *moves)
{
    if (disks == 0) {
        return;
    }
    hanoi(disks - 1, from, via, to, moves);
    (*moves)++;
    if (disks <= 3) {                    /* print only the small cases */
        printf("    move disk %d: %c -> %c\n", disks, from, to);
    }
    hanoi(disks - 1, via, to, from, moves);
}

/* --- binary search, recursive and iterative --- */
static long bsearch_rec(const int a[], long lo, long hi, int target)
{
    if (lo > hi) {
        return -1;                       /* base case: empty range */
    }
    long mid = lo + (hi - lo) / 2;       /* avoids overflow; week 7 */
    if (a[mid] == target) return mid;
    if (a[mid] <  target) return bsearch_rec(a, mid + 1, hi, target);
    return bsearch_rec(a, lo, mid - 1, target);
}

static long bsearch_iter(const int a[], long n, int target)
{
    long lo = 0, hi = n - 1;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] <  target) lo = mid + 1;
        else                  hi = mid - 1;
    }
    return -1;
}

/* --- Fibonacci three ways --- */
static long fib_naive(int n)
{
    call_counter++;
    if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

static long fib_memo(int n, long cache[])
{
    call_counter++;
    if (n <= 1)        return n;
    if (cache[n] != 0) return cache[n];
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
    return cache[n];
}

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

/* --- how deep can we go? --- */
static int max_depth = 0;
static void probe(int depth)
{
    max_depth = depth;
    if (depth < 200000) {
        probe(depth + 1);
    }
}

int main(void)
{
    puts("== frames build up, then unwind ==");
    factorial(4, 0);

    puts("\n== Towers of Hanoi ==");
    for (int disks = 1; disks <= 4; disks++) {
        int moves = 0;
        if (disks <= 3) printf("  %d disks:\n", disks);
        hanoi(disks, 'A', 'C', 'B', &moves);
        printf("  %d disks -> %d moves (2^%d - 1)\n", disks, moves, disks);
    }

    puts("\n== binary search: recursive and iterative agree ==");
    int sorted[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
    const long n = (long)(sizeof sorted / sizeof sorted[0]);
    const int targets[] = { 23, 2, 91, 7 };
    for (size_t i = 0; i < 4; i++) {
        printf("  %2d -> recursive %2ld, iterative %2ld\n",
               targets[i],
               bsearch_rec(sorted, 0, n - 1, targets[i]),
               bsearch_iter(sorted, n, targets[i]));
    }
    printf("  depth for %ld elements is about log2(%ld) = 4\n", n, n);

    puts("\n== the Fibonacci trap ==");
    const int fn = 30;

    call_counter = 0;
    clock_t t0 = clock();
    long r1 = fib_naive(fn);
    double d1 = (double)(clock() - t0) / CLOCKS_PER_SEC;
    printf("  naive  fib(%d) = %ld  in %8.4fs, %ld calls\n",
           fn, r1, d1, call_counter);

    long cache[64];
    memset(cache, 0, sizeof cache);
    call_counter = 0;
    t0 = clock();
    long r2 = fib_memo(fn, cache);
    double d2 = (double)(clock() - t0) / CLOCKS_PER_SEC;
    printf("  memo   fib(%d) = %ld  in %8.4fs, %ld calls\n",
           fn, r2, d2, call_counter);

    t0 = clock();
    long r3 = fib_iter(fn);
    double d3 = (double)(clock() - t0) / CLOCKS_PER_SEC;
    printf("  iter   fib(%d) = %ld  in %8.4fs, 0 recursive calls\n",
           fn, r3, d3);

    puts("\n== how deep before the stack runs out ==");
    puts("  (uncomment the probe call below and watch it die)");
    /* probe(1); printf("reached %d\n", max_depth); */

    return EXIT_SUCCESS;
}

gcc -std=c17 -Wall -Wextra -g -o recur recur.c
./recur

Watch the frames in GDB

This is the exercise that makes week 17's diagram real. Break inside the base case and look at the stack.

gdb ./recur
(gdb) break factorial if n == 1
(gdb) run
(gdb) backtrace

#0  factorial (n=1, depth=3) at recur.c:12
#1  0x... in factorial (n=2, depth=2) at recur.c:17
#2  0x... in factorial (n=3, depth=1) at recur.c:17
#3  0x... in factorial (n=4, depth=0) at recur.c:17
#4  0x... in main () at recur.c:96

Four frames of the same function, each with its own n, all alive at once. Move between them and inspect their locals:

(gdb) frame 2
(gdb) print n
$1 = 3
(gdb) info frame
(gdb) finish

info frame prints the frame's address, so you can confirm each sits lower than the one below it — exactly the picture from week 17. finish runs until the current frame returns and shows the value it produced.

Find your actual depth limit

Uncomment the probe call and run it:

ulimit -s
./recur

Segmentation fault (core dumped)

Now find where it died:

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o recur_asan recur.c
./recur_asan

==1234==ERROR: AddressSanitizer: stack-overflow on address 0x7ffd...
    #0 0x... in probe recur.c:104

Then add char padding[1024]; to probe and try again. The depth drops by a factor of roughly twenty. Frame size, not call count, is what consumes the stack.

The numbers from the Fibonacci section

On a typical machine, fib_naive(30) makes about 2.7 million calls; fib_memo(30) makes 59. Both return 832 040. Raise fn to 40 and the naive version takes seconds while the other two remain instant. The recursion was never the problem — recomputing the same subproblem was.

6Common mistakes

8Where this leads

Week 19 moves to the other half of week 17's memory map. On the heap, lifetime is not managed for you: memory you take must be given back, at a moment you choose, exactly once. That responsibility is what makes weeks 19 and 20 the hardest pair in the course — and the recursion you just learned returns in week 33, where trees make it indispensable.