Recursion

It’s possible to write a function that calls itself. That’s called recursion, and it turns out to be exactly the right tool for problems that are naturally defined in terms of smaller versions of themselves.

Take validating a credit card number. Card processors run a check called the Luhn algorithm, and at its core is a simple operation: summing the digits of a number. To find the digit sum of 1234, take its last digit, 4, and add it to the digit sum of the number left after removing that digit, 123. The digit sum of 123 is found the same way: take its last digit, 3, and add it to the digit sum of 12. Keep going, and eventually you’re down to a single digit, which is its own digit sum.

Notice the structure of that solution: solve digit_sum(1234) by solving a smaller problem, digit_sum(123), which is solved by an even smaller one, digit_sum(12), until you reach a single digit. That’s the core pattern you see in recursion.

The two ingredients

When a function calls itself, it’s called a recursive function, and that call to itself is a recursive call. Every recursive function needs exactly two things:

1. A base case: a case simple enough to solve directly, with no further recursive calls.
2. A recursive case: a step that breaks the problem into a smaller version of itself, and makes a recursive call to solve that smaller version.

Here’s the function written out, with the recursive case on line 7 and the base case on lines 4-6 to stop the recursion:

On line 7, n % 10 gives the last digit of n (because it’s the remainder when you divide by 10), and n / 10 just removes that last digit.

To see how this code works, it’s instructive to trace how the calls in digit_sum(1234) unfold:

Each call waits for the call below it to return a value, then adds its own digit before returning that sum up to whoever called it.

The call stack

Recall from last lesson that each function call reserves private space on the stack. That space is called a stack frame. A stack frame doesn’t just hold local variables, it also holds other information, like where to store the return value, and which line of code to jump to once the function returns.

Each of the four calls above gets its own frame, and therefore, its own scope. n inside the call digit_sum(1234) is a separate variable from the n inside digit_sum(123). It’s not a shared variable getting overwritten.

When functions call other functions, or call themselves, the stack gets organized into stack frames, one frame per active call, stacked on top of each other in the order the calls happened. That stack of frames is often referred to as the call stack.

Stack overflow

Without the n < 10 base condition, the stack would keep growing, one frame per call. The call stack has a fixed size (usually a few megabytes), and a recursive function, with no base case, will eventually exhaust it and crash with a stack overflow.

This can also happen if the base case is there, but is not reachable from every recursive call. Say you write n == 0 as a base case and you are counting down by 2 at each recursive step. If such a function is called for an odd number, it’ll eventually skip past zero and the recursion will not terminate.

Tail recursion

If a recursive call is the last action performed in a function, it’s called a tail call. The following recursive call to digit_sum is not a tail call because the addition happens after the recursive call returns:

A function that has only tail calls is called a tail-recursive function. You can often turn a non-tail-recursive function into a tail-recursive one. For example, we can carry the “running total” forward as an extra parameter, instead of building it up after each call returns:

Here, acc is that extra parameter (short for accumulator). You always call this function like digit_sum_tail(1234, 0) here, with 0 passed to acc. The addition of each digit will now happen before the next recursive call, as part of the argument acc + n % 10. Once the sum is computed, it’s returned and passed straight up. This version of the function is tail recursive because there’s no work done after the call returns. Here’s a trace for digit_sum_tail(1234, 0):

Why care about tail recursion? After a tail-recursive call, there is no remaining work to do, so in principle there’s no reason to keep the old frame around, and the recursive call can just reuse it instead of stacking a new one on top. Some languages guarantee this optimization (called tail call optimization) and treat tail recursion as no different from a loop in terms of memory. C++ does not guarantee it, though some compilers perform it under certain optimization settings.

Converting tail recursion to loops

If a recursive function you’ve written turns out to be tail recursive, it can usually be rewritten as a while loop with the same logic. Here’s digit_sum_tail that way:

The correspondence is direct:

• The accumulator parameter acc becomes a local variable, updated on each iteration.
• The arguments passed through the recursive call digit_sum_tail(n / 10, acc + n % 10) translate into the two assignment statements inside the loop body.
• The base case n < 10 becomes the loop condition n >= 10.

Exactly the same logic, but without the frames stacking up.

When to reach for recursion

A function is a good candidate for recursion when the problem is naturally defined in terms of smaller instances of itself. On the other hand, if a loop expresses the logic just as clearly, a simple for or while loop is usually the better choice. Loops don’t consume stack space per iteration, so they’re also the safer default when you’re not sure how deep the recursion might go.