Recursion and the Call Stack

A function that calls itself

Some problems are naturally defined in terms of smaller versions of themselves. A directory contains files and more directories, a tree node has child trees, and "sort this list" can be answered by "sort each half, then merge".

Recursion, meaning a function calling itself on a smaller input, is the direct way to code that shape. Interviews assume you have it, because trees, graphs, and divide-and-conquer are all recursion territory. Without it, those traversals require managing an explicit stack of pending work by hand.

Every correct recursive function has two parts:

• a base case, an input small enough to answer immediately, with no further calls
• a recursive case, which reduces the problem, calls itself on the smaller version, and combines the result

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

factorial(4) computes 4 * factorial(3), which computes 3 * factorial(2), down to factorial(1) returning 1. Then the multiplications resolve on the way back up, giving 1, then 2, then 6, then 24.

Factorial of 10

The factorial function called on a value large enough to justify the long long return type.

#include <iostream>

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

int main() {
    std::cout << factorial(10) << "\n";
    return 0;
}

Output

3628800

Tracing factorial(3) by hand is the fastest way to see the two directions of the process:

Read the table downward for the descent and upward for the results coming back. The multiplication in n * factorial(n - 1) cannot happen until the inner call has finished, so every multiplication in a recursion like this one is performed on the way back out.

The long long return type from lesson 2-1 matters more here than it looks. Factorials grow ferociously, and while 10! fits an int easily, 13! already exceeds 2.1 billion, so an int version would silently overflow at a surprisingly small input.

What actually happens: stack frames

Recursion works because of the machinery from lesson 4-1, namely that every call gets its own set of parameters and locals. When factorial(4) calls factorial(3), the first call's n = 4 is not overwritten. A fresh frame with n = 3 is stacked on top of it, and the n = 4 frame sits paused, waiting for a result. The frames then unwind in reverse order as each call returns. Unit 6 names the memory region these frames live in, the stack.

Two consequences follow directly from that mechanism.

A missing or unreachable base case is fatal. Each call stacks another frame, the frames never unwind, and the few megabytes reserved for them run out, crashing the program with a stack overflow. In C++ this is a hard crash rather than a catchable exception like Python's RecursionError.

Depth is bounded. Recursing a million levels deep will overflow the stack even with a correct base case. For deep linear recursions, prefer a loop, and save recursion for branching structures like trees, where the depth stays shallow and the code is dramatically clearer. A balanced tree of a million nodes is only about 20 levels deep.

A second example, digit by digit: the digits of 1984 are its last digit, 1984 % 10 which is 4, plus the digits of 1984 / 10 which is 198. That integer division from lesson 2-2 discards the last digit, and the number 0 has a digit sum of 0, which is a ready-made base case.

Summing the digits of a number recursively

Peeling one digit off the end per call, using the remainder and integer division from lesson 2-2.

#include <iostream>

int sumDigits(int n) {
    if (n == 0) return 0;
    return n % 10 + sumDigits(n / 10);
}

int main() {
    std::cout << sumDigits(1984) << "\n";
    return 0;
}

Output

22

The two operators split the number cleanly. n % 10 is the last digit and n / 10 is the number with that digit removed, so combining them as n % 10 + sumDigits(n / 10) is the whole recursive case.

The base case has to be n == 0 rather than n < 10, because the shrinking division always ends at 0 and a digit sum of 0 for the number 0 is exactly the right answer. Note also that this version returns 0 for negative input rather than crashing, since -19 / 10 is -1 and then -1 / 10 is 0, though the remainders come out negative, so a production version would take the absolute value first.

Forgetting the base case

A recursive function with no base case does not hang quietly. Calls keep stacking a new frame each time until the stack's few megabytes run out, and the program crashes with a stack overflow, usually within a fraction of a second.

Each recursive call pushes a fresh frame holding its own parameters and locals. With no base case those frames never unwind, so the stack region fills and the program dies. The compiler cannot catch this in general, since whether a recursion terminates depends on runtime values.

The contrast with an infinite while loop is instructive. A loop really does run in constant memory and will spin forever, while infinite recursion consumes memory with every call, which is why it fails fast. A fast crash is arguably the better failure, because it is impossible to miss.