Chapter 36

Home

Thinking Recursively

Recursion is when a function calls itself. It sounds circular and useless until you realise that many problems contain smaller versions of themselves — and recursion lets you solve the small version, then build back up to the full answer.

The Two Rules of Recursion

Every recursive function needs exactly two parts:

1. Base case

The smallest version of the problem — one you can solve without recursing. Without this, the function calls itself forever (stack overflow).

2. Recursive case

Break the problem into a smaller version of itself, call yourself on that smaller version, then combine the result.

countdown(3) → print 3 countdown(2) → print 2 countdown(1) → print 1 countdown(0) → base! return Each call pushes a frame onto the call stack They unwind in reverse order

C++ — countdown

void countdown(int n) {
    // Base case
    if (n == 0) {
        cout << "Liftoff!\n";
        return;
    }
    // Recursive case
    cout << n << "...\n";
    countdown(n - 1);
}

Rust — countdown

fn countdown(n: i32) {
    if n == 0 {
        println!("Liftoff!");
        return;
    }
    println!("{}...", n);
    countdown(n - 1);
}

The Recursive Leap of Faith

When writing a recursive function, assume the recursive call already works correctly for the smaller input. Don't trace through the whole chain — trust that it returns the right answer, then use that answer to build yours. This is called the recursive leap of faith.

📐 How to think about it

Instead of tracing countdown(3) → countdown(2) → countdown(1) → ..., just ask: "If I already had a working countdown(n - 1), could I write countdown(n)?" The answer is yes — print n, then call it. That's all you need to verify.

Sum of a Range (Returning a Value)

Recursive functions often compute and return a value. Here's sum(n) returning the sum of numbers from 1 to n.

C++

int sum(int n) {
    if (n == 1) return 1;           // base
    return n + sum(n - 1);          // recursive
}

Rust

fn sum(n: i32) -> i32 {
    if n == 1 { return 1; }
    n + sum(n - 1)
}

🚨 Stack overflow is real

Every recursive call uses memory on the call stack. In C++, default stack size is ~8 MB. A function that recurses 10⁶ deep will overflow. Recursion depth in contests is typically safe up to ~10⁵ for simple functions, but problems with N > 10⁵ often need iteration or tail-call optimisation.

Key Takeaways

Practice