Recursion: A Function That Calls Itself

Start with the problem

Some problems contain a smaller copy of themselves. The factorial of n is n times the factorial of n minus one. A folder contains files and other folders. A sorted list can be searched by looking at its middle and then searching one half. For problems shaped like this, the simplest solution is a function that solves a small case directly and solves a larger case by calling itself on a smaller one:

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

This looks suspicious. If every call has a variable called n, how does the function keep them apart? The answer is in lesson 6: each call has its own frame, so each has its own n.

How the idea works

Two parts. Every recursive function has a base case, where the answer is known and no further call is made, and a recursive case, which reduces the problem to a smaller instance of the same problem and combines the result. Both are needed. Without a base case the calls never stop, and a recursive case that does not move toward the base case never reaches it.

Frames pile up, then unwind. The trace follows factorial(3). Steps 3 and 4 push a frame for each recursive call. Each waiting frame is paused in the middle of return n * factorial(n - 1), holding a multiplication that cannot happen until the call above it returns. Step 5 is the base case, which returns 1 without calling anything. Steps 6 and 7 unwind: each frame finishes its multiplication with the value handed back, and returns to the frame below.

Before and after. Work written before the recursive call happens on the way down, in call order. Work written after it happens on the way up, in reverse order. The multiplication in factorial is on the way up, which is why nothing is multiplied until the base case has been reached.

Thinking recursively. Do not trace every level in your head. Assume that the call on the smaller problem works, then ask two questions: what is the base case, and how do I combine the answer for the smaller problem into the answer for this one? This is the same argument as the loop invariants of lesson 4, applied to calls.

The loop alternative. The factorial can also be computed without recursion:

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

It uses one frame instead of one per level. For a simple counting problem like this one, the loop is the better choice. Recursion earns its place on problems shaped like trees.

Why it is correct

The argument is induction. The base case is correct by inspection. If factorial(n - 1) returns the right value, then n times that value is the right answer for n. So the function is correct for every input that eventually reaches the base case. Termination needs a separate check: each call reduces n by one, so any n reaches 1 or below after finitely many calls, and the test n <= 1 catches it. Frames keep each call's state separate, so the pending multiplications of the waiting calls are never disturbed by the calls above them.

What it costs

Time. factorial(n) makes n calls, so its time grows in proportion to n. Each call costs a few nanoseconds for pushing the frame and returning, which is slightly more than a loop iteration.

Space. Each level holds a frame on the stack, so memory also grows in proportion to n. A frame for this function takes tens of bytes, so an 8 MB stack allows a depth of many thousands of levels, but not millions.

The result type. An int cannot hold factorial(13), which is 6,227,020,800 and above the 2,147,483,647 limit from lesson 4, so the multiplication overflows, and signed overflow is undefined behavior. Using long long extends the range to factorial(20).

Repeated work. The naive Fibonacci function, fib(n) as fib(n - 1) plus fib(n - 2), recomputes the same values over and over. The number of calls grows exponentially, roughly like 1.6 to the power n. For n equal to 40 there are about 331 million calls, which takes on the order of a second or more, while a loop computes the same number in microseconds. The cure is to remember results already computed, a technique called memoization, or to use a loop.

Pitfalls and variations

No base case, or an unreachable one. Infinite recursion fills the stack and crashes with a stack overflow, as in lesson 6. Writing if (n == 1) instead of if (n <= 1) breaks factorial(0), because n then moves away from 1 forever, as the third check showed.

The result type again. Recursion that multiplies or adds quickly overflows small integer types without warning.

Hidden exponential cost. A function that calls itself twice per level deserves a second look. Count how many calls a small input makes before trusting it on a large one.

Hard to read in the debugger. A backtrace of a recursive function shows many identical frames. The gdb command backtrace 5 prints only the five innermost, and up and down move between frames, which lets you inspect each level's n.

Variations. In a tail call the recursive call is the very last thing the function does. With optimization, compilers can often reuse the frame and turn such a call into a jump, but C++ does not guarantee it. Mutual recursion has two functions calling each other. If the depth could be huge, convert the recursion to a loop with an explicit stack of your own, kept in the heap.

Where it is used

Recursion is the natural tool for trees and graphs, for parsing nested text such as expressions or JSON, for walking folders, and for divide-and-conquer algorithms such as merge sort, quicksort and binary search, which later modules cover. Compilers use it constantly to process nested code. When you meet a problem whose parts look like smaller versions of the whole, think of a base case and a recursive case.

The last lesson of this module, "Splitting a Program Across Files: Headers and Include Guards", returns to the compile-and-link story of lesson 1, and shows how the functions you now write are organized into several files.