Basics 0/97

Recursion · 1 of 3

Recursive functions

Write a recursive function from its base case and its smaller call, follow its frames on the call stack, count its calls and its depth, and store repeated answers in a memo.

4,548 words · 21 min read

Part 1 of 9 Recursive functions

Recursive functions

A recursive function is a function that calls itself. It handles an input in one of two ways. If the input is small enough, the function answers it directly. Otherwise it turns the problem into the same problem on one or more smaller inputs, calls itself on those, and builds its answer from what they return. We start with a small example: adding up the digits of a number.

The digits of 5072 add up to 5+0+7+2=145 + 0 + 7 + 2 = 14. To compute this recursively, we look for a smaller copy of the same task inside it. The number 5072 is 507 with a 2 written on the end, so its digit sum is the digit sum of 507, plus 2. The same step applies to 507 and then to 50. A single digit is its own digit sum, so the chain stops at 5:

digit_sum(5072)=digit_sum(507)+2=digit_sum(50)+7+2=digit_sum(5)+0+7+2=5+0+7+2=14\begin{aligned} \text{digit\_sum}(5072) &= \text{digit\_sum}(507) + 2 \\ &= \text{digit\_sum}(50) + 7 + 2 \\ &= \text{digit\_sum}(5) + 0 + 7 + 2 \\ &= 5 + 0 + 7 + 2 = 14 \end{aligned}

The function below does the same. It returns a single digit as it is. For a longer number, it calls itself on the number without its last digit and adds the last digit to the result:

Sign up to run
def digit_sum(n):
    if n < 10:
        return n
    return digit_sum(n // 10) + n % 10

print(digit_sum(5072))

n % 10 is the last digit of n, and n // 10 is n without its last digit: 5072 % 10 is 2 and 5072 // 10 is 507.

The if is the base case: an input small enough to answer directly, with no further call. The last line is the recursive case: it calls the function on a smaller input and finishes the answer with a little work of its own, here one addition.

The equations above follow the calls all the way down to 5, but writing the function does not need that. First decide exactly what the function returns: digit_sum(n) returns the sum of the digits of nn, for any n≥0n \ge 0. Then write the recursive case as if someone else will solve the smaller input correctly and hand you the answer. You do not need to know how they solve it. Your only job is to turn the input into a smaller one, or to answer it directly when it is already small. By the description, digit_sum(507) returns 12, so digit_sum(5072) only has to add 2.

Trusting the smaller call is safe when two things hold. The base case returns the right answer, and every recursive call is made on an input that is closer to the base case, so the chain of smaller and smaller inputs cannot go on forever. Here a number with two or more digits loses one digit in each call, so the calls reach a single digit and stop. A number with dd digits makes dd calls, 4 for 5072. If you have seen proofs by induction, assuming the smaller call is right is the induction hypothesis, and these two conditions are what make the proof work.