Recursion

Recursion looks magical the first time you see it, then becomes the most natural way to express many algorithms. The key is to TRUST the recursive call: assume f(n-1) already gives the right answer, and just figure out how to combine it with n.

How Recursion Actually Runs

Each call gets its own stack frame with its own local variables. C builds them up as you call, then unwinds them as you return.

factorial(3)
└── 3 * factorial(2)
        └── 2 * factorial(1)
                └── returns 1
        └── returns 2
└── returns 6

Each call WAITS for the inner call to finish, then completes its work. That's why too-deep recursion overflows the call stack (typically 1 MB — usually a few thousand to a few hundred-thousand frames depending on locals).

Writing a Recursive Function — Recipe

1. Identify the base case. What's the simplest input that has an obvious answer? 2. Trust the recursive call. Assume f(smaller) already works. 3. Combine. Use that result with the current input to build the answer.

Example — sum of digits of n:

int digit_sum(int n) {
    if (n < 10) return n;                  /* 1. base */
    return n % 10 + digit_sum(n / 10);     /* 3. combine last digit + rest */
}

Classic Examples

Factorial

int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

Fibonacci (slow but instructive)

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

This is exponentially slow — fib(40) already feels slow. Real code uses iteration or memoisation.

Power (a^b)

long power(int a, int b) {
    if (b == 0) return 1;
    return a * power(a, b - 1);
}

Greatest Common Divisor — Euclid

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Beautiful — three lines, ancient algorithm.

Reverse a String In Place

void reverse(char *s, int l, int r) {
    if (l >= r) return;
    char t = s[l]; s[l] = s[r]; s[r] = t;
    reverse(s, l + 1, r - 1);
}

Divide & Conquer

Many recursive algorithms split the input into halves, solve each, and combine. Examples: merge sort, quicksort, binary search.

int binsearch(const int *a, int lo, int hi, int target) {
    if (lo > hi) return -1;            /* not found */
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] <  target) return binsearch(a, mid + 1, hi, target);
    else                  return binsearch(a, lo, mid - 1, target);
}

Each call halves the problem — O(log n).

Backtracking — Try, Recurse, Undo

The pattern behind sudoku solvers, maze runners, N-queens:

for each choice:
    make choice
    if solve(rest) succeeds: return success
    undo choice
return failure

Skeleton (Tower of Hanoi):

void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);
    printf("Move disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, from, to);
}

hanoi(3, 'A', 'B', 'C') produces all 7 moves automatically.

Stack Depth — The One Thing to Watch

Each recursive call adds a frame. C's default stack is around 1 MB — about 100k–500k deep frames. Recursing on a 1-million-element list iteratively is fine; recursing on it can overflow.

If you ever see a "stack overflow" or segfault on a recursive program, that's the cause.

Tail Recursion

A recursive call is in tail position if it's the LAST thing the function does:

/* TAIL recursive — return value used directly */
int tail_sum(int n, int acc) {
    if (n == 0) return acc;
    return tail_sum(n - 1, acc + n);
}
/* NOT tail — must wait to multiply after the call returns */
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

A clever compiler may optimise tail calls into a loop (no stack growth). C compilers MAY do this with optimisation enabled, but the standard doesn't guarantee it. So in C, prefer iteration when depth could be huge.

When NOT to Use Recursion in C

Once recursion clicks, trees, graphs, parsing, and divide-and-conquer all fall into place. Trust the recursive call.