Recursion

Recursion is when a function calls itself, directly or indirectly, to solve a problem by breaking it into smaller instances of the same problem. Every correct recursive function needs two ingredients: a base case that stops the recursion, and a recursive case that makes progress toward that base case.

Base Case and Recursive Case

Base case — the simplest possible input, handled directly without further recursive calls. This is what stops the recursion.
Recursive case — the function calls itself with a smaller or simpler version of the input, moving it closer to the base case.

Classic Example: Factorial

The factorial of n (written n!) is defined as n * (n-1)!, with the base case 0! = 1. This definition translates almost directly into code.

Factorial via recursion

#include <stdio.h>

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

int main(void) {
    for (int i = 0; i <= 5; i++) {
        printf("%d! = %d\n", i, factorial(i));
    }
    return 0;
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

Classic Example: Fibonacci

The Fibonacci sequence has two base cases and demonstrates a function making more than one recursive call.

Fibonacci via recursion

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;      // base case 1
    if (n == 1) return 1;      // base case 2
    return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}

int main(void) {
    for (int i = 0; i < 8; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

0 1 1 2 3 5 8 13

This Fibonacci is inefficient

The recursive Fibonacci above recomputes the same values many times (`fibonacci(n-2)` is computed independently by both `fibonacci(n)` and `fibonacci(n-1)`), giving it exponential running time. It is a great teaching example, but a loop-based or memoized version is far more efficient for real use.

The Danger of Unbounded Recursion

Each recursive call uses a new stack frame to store its parameters, local variables, and return address. If the base case is missing, wrong, or simply never reached, the function keeps calling itself until it exhausts the call stack.

Missing base case — do not run this

int broken(int n) {
    return n + broken(n - 1); // no base case: never stops
}

Stack overflow is undefined behavior in C

Unlike languages such as Python, which raise a clean, catchable `RecursionError` when recursion goes too deep, C has no built-in recursion-depth check at all. Unbounded or excessively deep recursion simply keeps consuming stack memory until it runs past the space the operating system gave the program's stack. At that point the behavior is undefined: on most systems the program crashes (a segmentation fault), but it can also corrupt memory silently depending on the platform. There is no exception to catch and no guaranteed clean error message — you must prevent this yourself by always guaranteeing a reachable base case.

Recursion vs Iteration in C

Many recursive functions can be rewritten as loops. In C specifically, iteration is often preferred for performance- or safety-sensitive code.

Factorial rewritten iteratively

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

Recursion	Iteration
Uses one stack frame per call — risk of stack overflow	Uses constant stack space regardless of iteration count
Function-call overhead on every step	No per-step call overhead
Often clearer for naturally recursive problems (trees, divide-and-conquer)	Often clearer and faster for simple counted or accumulating loops
C compilers may optimize some tail calls, but this isn't guaranteed by the C standard	Behavior is predictable and portable across compilers

Always identify the base case first, and make sure every recursive call moves strictly closer to it.
In C, prefer iteration for simple counted loops, and for code where stack depth is a concern (e.g. processing very large or attacker-controlled input sizes).
Reserve recursion for problems that are naturally recursive, like tree traversal, divide-and-conquer algorithms, and backtracking.

Next: local variables

The next page looks at *function scope* — why local variables (including the parameters and locals used in every recursive call) do not persist between calls, and how the stack makes that possible.