C Mastery / Recursion and Function-Call Mechanics
Part 1 — The Core Language

Recursion and Function-Call Mechanics

This chapter covers recursion in C and the mechanics of the call stack that make it possible. It connects the abstract idea of a function call to the concrete reality of stack frames.

Why This Matters

Recursion is a natural way to express many algorithms (tree traversal, parsing, divide-and-conquer), but it consumes stack space. Understanding how the stack grows and shrinks lets you predict when recursion is safe and when it will overflow the stack.

Prerequisites

Core Concept

A function may call itself, directly or indirectly. Each call creates a new stack frame (activation record) holding the function's parameters, local variables, and return address. When the function returns, its frame is reclaimed.

Recursion requires:

1. A base case that does not recurse. 2. A recursive case that makes progress toward the base case.

Without a base case (or if progress is not guaranteed), recursion never terminates and eventually overflows the stack.

Syntax

unsigned factorial(unsigned n)
{
    if (n <= 1)
        return 1;              /* base case */
    return n * factorial(n - 1); /* recursive case */
}

Examples

Factorial (recursive)

#include <stdio.h>

unsigned factorial(unsigned n)
{
    if (n <= 1)
        return 1;
    return n * factorial(n - 1);
}

int main(void)
{
    printf("%u\n", factorial(5));
    return 0;
}

Expected output: 120.

Factorial (iterative, for comparison)

unsigned factorial_iter(unsigned n)
{
    unsigned result = 1;
    for (unsigned i = 2; i <= n; i++)
        result *= i;
    return result;
}

Fibonacci (showing exponential blowup)

unsigned fib(unsigned n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);  /* O(2^n) */
}

This is correct but inefficient. A memoized or iterative version is preferred for large n.

How It Works

Each call pushes a frame onto the call stack. The frame contains, roughly:

When a function returns, the stack pointer moves back, reclaiming the frame. The stack has a finite size (implementation-defined, often a few MB on hosted systems), so deep recursion can overflow it.

Variations

Tail recursion

A function is tail-recursive if the recursive call is the last thing before returning, with no pending computation. Some compilers optimize tail recursion into a loop (tail-call optimization), avoiding stack growth. C does not *require* this optimization.

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);  /* tail call */
}

Mutual recursion

Two or more functions call each other. This requires a forward declaration for at least one.

int is_even(int n);
int is_odd(int n) { return n == 0 ? 0 : is_even(n - 1); }
int is_even(int n) { return n == 0 ? 1 : is_odd(n - 1); }

Common Mistakes

Undefined Behavior

program then accesses memory beyond the stack, the behavior is undefined. (There is no portable way to catch stack overflow in ISO C.)

value that overflows unsigned is fine — it wraps — but with int it is UB).

Portability

ulimit -s on POSIX).

correctness.

Under the Hood

On x86-64, call pushes the return address and jumps; ret pops it. The stack grows downward (toward lower addresses) on x86 and most ARM. Local variables are accessed via the base pointer or stack pointer. Part 7 covers this in detail.

Practical Usage

pressure.

(e.g., tree traversal of very deep trees).

Exercises

1. Write recursive and iterative factorial functions and compare results. 2. Write a recursive binary search and prove it terminates. 3. Write a recursive tree traversal and measure the depth at which stack overflow occurs (carefully, on a small program). 4. Convert a tail-recursive function to an explicit loop and compare.

Deep Challenge

Implement an iterative post-order tree traversal using an explicit stack, and explain why this approach avoids stack overflow for very deep trees where a recursive traversal would fail. Discuss the trade-offs (complexity vs. stack safety).

References

Verification

standard-guaranteed check. VERIFIED

verified.`

Progress

Concept checkboxes

Mastery levels

ConceptCurrent level (0–8)Target level
c.func.recursion05
← PrevNext →