Recursion

Recursion is when a function defines itself in terms of itself — the function calls itself, with progressively smaller inputs, until it hits a base case that can be solved directly. The repeated self-application then unwinds, combining the small results into the answer for the original input.

Two pieces every recursive function must have:

Base case: an input small enough to solve directly without recursing further.
Recursive case: a way to express the problem in terms of a smaller version of itself.

Without a base case, the recursion never terminates and you get a stack overflow. Without a recursive case, it’s just a regular function.

Classic example: factorial

The factorial $n!$ has the textbook recursive structure:

Base case: $1! = 1$ (or $0! = 1$ ).
Recursive case: $n! = n \cdot (n - 1)!$ .

int fact(int n) {
    if (n == 0 || n == 1) return 1;     // base case
    return n * fact(n - 1);              // recursive case
}

For fact(5): the call chain is fact(5) → fact(4) → fact(3) → fact(2) → fact(1). The last call returns 1; then fact(2) returns 2 * 1, fact(3) returns 3 * 2, etc. Final result: 120.

Iterative vs. recursive

The same factorial can be done iteratively:

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

When to choose which:

Iterative: more memory-efficient (no stack frames per step), often slightly faster.
Recursive: cleaner code when the problem has natural recursive structure (trees, divide-and-conquer).

For factorial, iteration wins on simplicity. For tree traversal, recursion is dramatically simpler.

Recursion on data structures

Recursion is the natural way to walk recursive data structures:

Trees: traverse(node) = process(node) + traverse(node.left) + traverse(node.right). See Binary tree traversal.
Linked lists: process current node + recurse on next.
Filesystem directories: process this directory + recurse into each subdirectory.

Example: recursively insert a value into a sorted linked list:

int insert(struct node **list, int value) {
    if (*list == NULL || (*list)->value > value) {
        *list = newNode(value, *list);    // create new node, link to current head
        return 1;
    } else if ((*list)->value == value) {
        return 0;                          // already in list
    } else {
        return insert(&((*list)->next), value);   // recurse
    }
}

The recursive call descends one node deeper into the list. The base case is “found the right spot” or “reached the end.”

How recursion uses the stack

Each recursive call creates a new Stack frame on the call stack holding that call’s local variables and return address. When the call returns, its frame is popped.

For fact(5), the stack at maximum depth has 5 frames stacked — one per recursive call. When fact(1) returns, frames pop in reverse order: 1, 2, 3, 4, 5.

This means deep recursion costs memory. A function recursing 10,000 times needs 10,000 stack frames. If the stack is 1 MB and each frame is 100 bytes, you get ~10,000 frames before overflow.

For very deep recursion, convert to iteration or use tail recursion (see below) if your compiler supports tail-call optimization.

Tail recursion

A tail-recursive function returns the result of its recursive call directly, with no further computation. The naïve factorial isn’t tail-recursive (it multiplies after the recursive call returns):

return n * fact(n - 1);   // multiplication happens after return

A tail-recursive version uses an accumulator:

int factHelper(int n, int acc) {
    if (n <= 1) return acc;
    return factHelper(n - 1, n * acc);   // recursive call is the last thing
}
int fact(int n) { return factHelper(n, 1); }

When the recursive call is the last operation, an optimizing compiler can reuse the current stack frame instead of pushing a new one — converting the recursion into a loop in disguise. Programs with tail-recursive functions can recurse arbitrarily deep without stack overflow.

Modern C compilers (GCC, Clang) reliably perform tail-call optimization at -O2 and above; the C standard doesn’t require it, so unoptimized debug builds typically don’t, and you shouldn’t rely on it for correctness on deep recursion. Functional languages (Scheme, Erlang) guarantee it as part of the language semantics.

Where recursion shines

Tree algorithms: traversal, search, insertion in BSTs and AVL trees.
Divide-and-conquer: Merge sort, Quick sort.
Backtracking: maze solving, N-queens, Sudoku.
Mathematical definitions: Fibonacci, GCD, Ackermann.

Multiple recursion

Some recursive functions call themselves more than once per invocation. Naive Fibonacci:

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

fib(5) calls fib(4) and fib(3). Each of those calls more. The call tree branches dramatically — fib(n) makes about $ϕ^{n}$ total calls (where $ϕ \approx 1.618$ , the golden ratio).

This is exponentially slow. The exact wall-clock numbers vary by orders of magnitude — fib(40) might take milliseconds in C, fractions of a second in JavaScript, several seconds in Python. What’s universal is the scaling: each increment of $n$ multiplies the running time by roughly $ϕ \approx 1.618$ . So fib(50) is about $ϕ^{10} \approx 123$ times slower than fib(40) whatever language you’re in. The reason: massive redundant recomputation. fib(3) is computed in many subtrees of fib(5)’s call.

Two fixes:

Memoization: cache each result. Subsequent calls for the same $n$ return the cached value. Reduces complexity to $O (n)$ .
Iterative computation: compute fib(0), fib(1), fib(2), …, fib(n) in order, keeping only the last two values. $O (n)$ time, $O (1)$ space.

Most “nicely recursive” mathematical definitions are like this — beautiful, slow, easily fixed with memoization.

Mutual recursion

Two functions calling each other. Example: parsing.

int parseExpr() { ... parseTerm(); ... parseExpr(); ... }
int parseTerm() { ... parseExpr(); ... parseFactor(); ... }

Functions are mutually recursive when their call graphs include cycles. Same termination argument as direct recursion: each call must eventually reach a base case.

Common in:

Recursive descent parsers: nonterminals call each other.
State machines with multiple state procedures.
Game logic where two parties take turns.

Recursion vs iteration: when each wins

Property	Recursion	Iteration
Memory	$O (depth)$ stack frames	$O (1)$
Speed	Slightly slower (function call overhead)	Slightly faster
Code clarity	Often clearer for tree/divide-and-conquer	Often clearer for linear/sequential
Risk	Stack overflow on deep recursion	Off-by-one errors in loop bounds

Pick recursion when:

The problem has natural recursive structure (trees, divide-and-conquer, recursive math).
Recursion makes the code dramatically clearer.
The recursion depth is bounded and small (no millions of frames).

Pick iteration when:

Performance is critical.
The recursion would be very deep.
The recursion is “linear” — each call makes one recursive call (a glorified loop).

When recursion goes wrong

Three common failure modes:

No base case: infinite recursion → stack overflow.

int bad(int n) { return bad(n + 1); }   // never returns

Base case never reached: e.g., recursing on $n - 2$ from $n = 5$ but base case is $n = 0$ . Skip past the base case, recurse forever.
Exponential explosion: naive multiple recursion (like Fibonacci) repeats work catastrophically. Memoize.

Debugging recursive code: add a print statement at function entry showing the input. Run with a small input. Check that the call sequence is what you expect, that base cases trigger, and that results combine correctly.

A philosophical note

Recursion is one of those concepts that “clicks” suddenly. Before clicking: the idea of a function calling itself feels paradoxical or magical. After clicking: it’s just one tool among many.

The trick is to trust the recursion — when writing the recursive case, assume the recursive call returns the correct answer for its smaller input. Don’t trace into it mentally. Just combine the smaller answer with the current step.

This is the same kind of trust as mathematical induction: if the base case works, and each step preserves correctness, the whole induction works. You don’t have to follow it all the way down — just verify each piece.

For the iterative alternative for trees (using an explicit queue), see Breadth-first search. For divide-and-conquer in action, see Merge sort and Quick sort. For the underlying call-stack mechanics, see Stack (computing) and Stack frame.

Idriss Rami — Notes

Explorer