Recursion

The anatomy of a recursive function

Every recursive function has two essential parts. The base case is the condition that stops the recursion: when reached, the function returns a value without calling itself. The recursive case is the body that solves a smaller version of the same problem and calls the function with a smaller argument, making progress toward the base case. Without a reliable base case, the function calls itself forever — causing a stack overflowand a program crash.

Factorial (n!) is the textbook example: 4! = 4 × 3 × 2 × 1 = 24. The mathematical definition is already recursive — n! = n × (n−1)! — and the code mirrors it exactly:

// Fragile version — crashes if n is 0 or negative:
long long factorial(int n) {
    if (n == 1) return 1LL;     // base case
    return n * factorial(n - 1); // recursive case: smaller problem
}

// Safer version — unsigned type prevents negative n; handles 0! = 1:
unsigned long long factorial(unsigned int n) {
    if (n <= 1) return 1ULL;         // base case: 0! = 1! = 1
    return n * factorial(n - 1);
}

// factorial(4) unwinds like this:
//   factorial(4) = 4 * factorial(3)
//   factorial(3) = 3 * factorial(2)
//   factorial(2) = 2 * factorial(1)
//   factorial(1) = 1              ← base case, returns 1
//   Back up: 2*1=2, 3*2=6, 4*6=24

Notice that the first version would loop forever if called with 0 or a negative number — the recursion would go 0, -1, -2, … and never hit the n == 1 base case. Changing the parameter to unsigned int makes that class of error impossible, and changing the base case to n <= 1 covers both 0! and 1!.

How the call stack works during recursion

Every function call — recursive or not — adds a stack frameto the call stack. A frame holds the function's local variables, its parameters, and the return address (where execution should resume after the function finishes). When a recursive function calls itself, it pushes another frame on top. This continues until the base case is reached, at which point the frames unwind one by one, each returning its result to the caller below it.

// Call stack during factorial(4):
//
//  ┌────────────────────┐  ← top of stack (most recent call)
//  │ factorial(1) → 1   │  ← base case: returns 1
//  ├────────────────────┤
//  │ factorial(2) → 2*1 │  ← waits for factorial(1), then returns 2
//  ├────────────────────┤
//  │ factorial(3) → 3*2 │  ← waits for factorial(2), then returns 6
//  ├────────────────────┤
//  │ factorial(4) → 4*6 │  ← waits for factorial(3), then returns 24
//  └────────────────────┘  ← original call
//
// Each frame consumes memory. For factorial(1000), 1000 frames are
// pushed. Most platforms allow thousands to tens of thousands of frames
// before running out of stack space.

The call stack is finite. If your recursion is too deep — say, computing factorial(1'000'000) — you will run out of stack space and the program will crash with a stack overflow. For very deep problems, an iterative solution (explicit loop) or an iterative approach using your own stack data structure is safer.

A richer example: powers with negative exponents

Recursion can handle more than one case at a time. Here is a power() function that correctly handles zero, positive, and negative exponents through three separate branches, each of which either returns directly or recurses with a smaller problem:

double power(double x, int n)
{
    if (n == 0)      return 1.0;                   // base case: x^0 = 1
    else if (n > 0)  return x * power(x, n - 1);  // x^n = x * x^(n-1)
    else             return 1.0 / power(x, -n);    // x^-n = 1 / x^n
}

// powers of 8 from -3 to +3:
// 0.00195312  0.015625  0.125  1  8  64  512

All three branches make progress toward n == 0: positive exponents decrease n by 1 each call, and negative exponents negate n (making it positive), then let the positive branch handle the rest.

Recursive algorithms — divide and conquer

Many important algorithms are naturally recursive: they split a problem into two smaller versions of the same problem, solve each half recursively, and combine the results. This strategy is called divide and conquer. Binary search, merge sort, quicksort, and tree traversal all follow this pattern.

Quicksort is a good example. Given a list, choose a pivot element, rearrange so everything less than the pivot is to its left and everything greater is to its right, then recursively sort each side. The base case is a list of zero or one elements — it is already sorted:

// Conceptual structure of quicksort:
void quicksort(std::vector<int>& v, std::size_t start, std::size_t end)
{
    if (!(start < end)) return;   // base case: 0 or 1 elements — already sorted

    // Partition: move pivot to position 'mid', smaller left, larger right
    std::size_t mid = partition(v, start, end);

    // Recursively sort each half:
    if (mid > start) quicksort(v, start, mid - 1);   // left of pivot
    if (end > mid)   quicksort(v, mid + 1, end);      // right of pivot
}

// A non-recursive wrapper so callers don't need to pass indices:
void quicksort(std::vector<int>& v) {
    if (!v.empty())
        quicksort(v, 0, v.size() - 1);
}

The wrapper pattern — a public function with a convenient signature that calls a private recursive function with the full parameters — is common in recursive code. Users call quicksort(v); the recursion itself uses index parameters to track which portion of the vector it is currently sorting.

Recursion vs. iteration — when to choose which

Any recursive function can be rewritten as an iterative one (using loops), and vice versa. The choice between them is usually a matter of clarity and performance:

A performance note: many C++ compilers are capable of transforming tail-recursive functions — where the recursive call is the very last thing the function does — into loops automatically. A tail-recursive factorial or power may compile to code no slower than the loop version. However, not all recursion is tail-recursive, and you cannot rely on this optimisation in portable code.

// Iterative factorial — equivalent result, no stack growth:
unsigned long long factorial_iter(unsigned int n) {
    unsigned long long result {1};
    for (unsigned int i {2}; i <= n; ++i)
        result *= i;
    return result;
}

// Tail-recursive factorial — accumulates result in a parameter:
unsigned long long factorial_tail(unsigned int n, unsigned long long acc = 1) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // last operation is the recursive call
}

Key rules to remember