Recursive definitions
Some things are easiest to describe in terms of a smaller version of themselves. Take the factorial of a whole number , written . It is , so . Look at what contains: is , so . That holds for every , which gives a second way to define the factorial, with two rules:
The first rule works out from the factorial just below it. On its own it would never finish: needs , which needs , and so on down past 0 into . The second rule stops the chain by giving one answer outright. ( is chosen so that the first rule gives .)
A definition like this, which uses a smaller case of the thing being defined, is recursive. A function can work the same way: its body can call the very function being defined.
Definition
A recursive function is a function that calls itself.
The base case and the recursive case
Here are the two rules written as a function:
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)
print(fact(4))
print(fact(0))The if is the base case: an input small enough to answer without calling fact again, here . The last line is the recursive case: it asks fact for and multiplies the answer by . Each call passes an input one smaller than its own, so starting from 4 the calls go 4, 3, 2, 1, 0 and stop.
This AtCoder problem defines a function by exactly these two rules, which makes it a good first recursive program to submit. Read with int(input()) and print fact(N):
A function is defined on whole numbers by two rules: , and for every . Given , print .
Constraints
- is an integer
Sample 1 · Input
2
Output
2
Sample 2 · Input
3
Output
6
Sample 3 · Input
0
Output
1
Sample 4 · Input
10
Output
3628800
The same function written with a loop
You could also compute a factorial with a while loop. Here are both versions side by side:
def fact_loop(n):
result = 1
k = n
while k > 0:
result = result * k
k = k - 1
return result
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)
print(fact_loop(5), fact(5))The loop keeps its progress in two names that change on every pass, result and k. The recursive version never changes a name. Its progress is the chain of calls, each with its own n, and the multiplications happen as those calls return. The next part shows this step by step.
For the factorial, the loop is just as good. Recursion pays off on problems that break into smaller copies of themselves in a way one loop can't follow. Near the end of this lesson you'll print every number with digits, where comes from the input: loops would need one nested loop per digit, while one recursive function handles any .
One frame for each recursive call
Every call opens a new frame for its parameters, and the frames of calls still waiting form the call stack. A recursive call is no different. While fact(3) runs, it calls fact(2), and that call gets a frame of its own with its own n, equal to 2, so the n in the first frame stays 3. Step through it below: frames pile up as the calls go down, and come off one at a time as the answers come back up.
Step through fact(3)
At the deepest step of fact(3), four fact frames are open, and the three below the top are paused halfway through n * fact(n - 1). When fact(0) returns 1, fact(1) finishes , fact(2) finishes and fact(3) finishes . The multiplications happen on the way back up, in reverse order of the calls.
The fact(0) preset reaches the base case on the very first call. The fact(-1) preset never reaches it: the input does get smaller, but moves away from 0, so the calls go on until the program runs out of room for frames.
The recursive leap of faith
Stepping through the calls shows you what happens, but it's slow: fact(3) already takes fourteen steps, and fact(10) would take 35. So when you write or check a recursive function, you don't trace it. You take what is called the recursive leap of faith: while writing the recursive case of fact(n), assume that fact(n - 1) already returns the right answer, . All that's left is to turn into , which takes one multiplication by .
The leap is safe as long as the base case is right and the calls keep moving toward it. fact(0) is right because the base case says so. fact(1) is right because it multiplies a correct fact(0) by 1, fact(2) is right because fact(1) is, and so on up to any you like. So to check a recursive function, check the base case, and check that the recursive case turns a right answer for the smaller input into a right answer for this one. Mathematicians call this argument a proof by induction.
Deeper read: two functions that call each other
A function can also reach itself through a second function: a calls b, and b calls a. This is mutual recursion, and it fits a task that switches back and forth between two rules.
Here is one. Take the digits of a number from the right and alternately add and subtract them: for 2026 that gives . A number is divisible by 11 exactly when this alternating sum is; for 918,082 the sum is , and .
add_last(n) adds the last digit, n % 10, and hands the rest of the number, n // 10, to subtract_last, because the next digit must be subtracted. subtract_last does the opposite and hands the rest back to add_last.
def add_last(n):
if n == 0:
return 0
return n % 10 + subtract_last(n // 10)
def subtract_last(n):
if n == 0:
return 0
return -(n % 10) + add_last(n // 10)
print(add_last(2026))
print(add_last(918082))Python details
add_last mentions subtract_last above its def. Python looks the name up when the call runs, and by then both def lines have run.
Each function removes one digit before calling the other, so the number reaches 0, the base case of both. The leap of faith works here too: trusting that subtract_last(202) returns , add_last(2026) returns .
For this task one function would do the same job: alternating(n) can return n % 10 - alternating(n // 10). Two functions are clearer when the two rules are long and different. A calculator that reads expressions such as 2 * (3 + 4) can use three functions, expression, term and factor, and a factor in parentheses calls expression again.
The limit on recursion depth
Every call that is still waiting keeps its frame, so at its deepest fact(n) has frames open at once, from fact(n) down to fact(0). The number of frames a recursion has open at once is its depth. Frames take memory, so the depth can't grow without limit.
Python sets the limit itself: once about 1,000 frames are open, it stops the program with a RecursionError. That is how the fact(-1) preset would end if you let it run. The limit is there so that a recursion that never ends stops with a clear message instead of crashing Python.
Going ten thousand calls deep
A recursion that has to go deeper than about 1,000 calls needs a higher limit, which sys.setrecursionlimit sets. sum_to(n) adds by calling sum_to(n - 1), so sum_to(10000) is 10,001 calls deep, ten times past the default. It works once the limit is 20,000:
sys.setrecursionlimit(20000)
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(10000))Don't raise the limit to a huge number out of habit. Python's documentation warns that a limit set too high can crash Python itself instead of raising an error.
Deeper read: why Python keeps a frame for every call
Look at sum_to again. When sum_to(n - 1) returns, the call still has work to do: it adds . Compare a version that carries the running total in a second parameter instead:
def sum_rest(n, total):
if n == 0:
return total
return sum_rest(n - 1, total + n)
print(sum_rest(10, 0))Here the recursive call is the last thing the function does: it hands back the result unchanged. A call like that is a tail call. After a tail call the caller's frame holds nothing it still needs, so a language could reuse that frame for the new call, and the whole recursion would then run in one frame, like a loop.
Python never does this, so sum_rest(10000, 0) hits the recursion limit just as sum_to(10000) does. Guido van Rossum, who created Python, explained why in an April 2009 post on his blog, Neopythonic. The reused frames would vanish from the traceback Python prints when a program fails, and he wanted those tracebacks complete for debugging. And once programs relied on the reuse, they would break on any Python implementation that didn't do it. He added that a limit of about 1,000 is plenty for walking a tree, such as a parsed program, though not for a loop over a long list written as recursion.
Printing on the way down and on the way back up
So far each call did its work after its recursive call returned: fact multiplies on the way back up. A call can also work before its recursive call, and with printing you can see the difference in the output.
echo(n) prints n, calls echo(n - 1) if , and then prints n again. Before you step through it, try to predict what echo(3) prints.
Step through echo(3)
The first print in each call runs before the call below it starts, so those come out on the way down: 3, 2, 1. The second print waits until every call below has finished, so those come out on the way back up: 1, 2, 3. Altogether echo(3) prints 3, 2, 1, 1, 2, 3.
Printing 1 2 1 3 1 2 1 with two calls
Put a print between two recursive calls, and a function can write out a sequence that is itself defined recursively. This problem defines one:
The sequences are defined like this: is the single number 1, and for , is , then the number , then again. So is 1, 2, 1 and is 1, 2, 1, 3, 1, 2, 1. Given , print with spaces between the numbers.
Constraints
- is an integer
Sample 1 · Input
2
Output
1 2 1
Sample 2 · Input
1
Output
1
Sample 3 · Input
4
Output
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
Let show(n) print . Take the leap of faith and assume show(n - 1) prints correctly. Then the recursive case is the definition itself: show(n - 1), then print , then show(n - 1) again. For the base case we can go one step below the problem: show(0) prints nothing, so show(1) prints nothing, then 1, then nothing, which is .
def show(n):
if n == 0:
return
show(n - 1)
print(n, end=" ")
show(n - 1)
n = int(input())
show(n)
print()Python details
end=" " ends each printed number with a space instead of a new line, and the final print() ends the line. The judge ignores the trailing space.
Each step doubles the sequence and adds one number, so has numbers, 65,535 for . Yet the calls nest only 17 deep, from show(16) down to show(0).
Tree recursion: more than one recursive call
show makes two recursive calls, so its calls no longer form one chain: each call branches into two, like a tree. A function whose calls can make two or more recursive calls uses tree recursion. The classic example is the Fibonacci numbers. They start with 0 and 1, and each later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13. The definition refers to itself twice, and so does the function:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))The demo draws the tree of calls. Pick an and step through the order the calls happen in:
fib(4) finishes the whole branch under fib(3) before it starts on fib(2). So the frames open at any moment form one path from the top of the tree down to the current call, and the depth is at most .
The number of calls grows much faster than the depth. fib(2) appears twice in the tree for fib(4), and bigger trees repeat the same calls many more times:
| Calls | ||
|---|---|---|
| 10 | 55 | 177 |
| 20 | 6,765 | 21,891 |
| 30 | 832,040 | 2,692,537 |
| 35 | 9,227,465 | 29,860,703 |
Each step of 5 in multiplies the calls by about 11, so fib(40) makes 331,160,281 calls to work out a number that a loop gets in 40 additions. The function is correct but slow. Remembering each answer the first time it is computed makes it fast.
Counting partitions by splitting on one choice
fib's two calls keep asking the same questions. Tree recursion is at its best when the branches ask different questions, and counting is where that happens most. Here is a counting question: in how many ways can you write 5 as a sum of whole numbers no bigger than 3, if the order doesn't matter? Listing them gives five:
Each of these is a partition of 5 with parts at most 3. The number 30 has 5,604 partitions, far too many to list, so we want count_partitions(n, m) to count the partitions of with parts at most without listing them.
Split the partitions into two groups with one yes-or-no question: does the partition use a part equal to ? With and :
- Yes: 3 + 2 and 3 + 1 + 1. Take one 3 away and you're left with 2 and 1 + 1, which are exactly the partitions of with parts at most 3.
- No: 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1. These are exactly the partitions of 5 with parts at most 2.
Every partition lands in exactly one group, so the count is the sum of the two groups' counts, and each of those is a smaller question of the same kind:
For , that gives . The calls make or smaller, so three base cases cover where they end up. means the parts taken away added up exactly: one partition. A negative means the last part was too big: none. with still positive means no parts are allowed: none.
def count_partitions(n, m):
if n == 0:
return 1
if n < 0 or m == 0:
return 0
return count_partitions(n - m, m) + count_partitions(n, m - 1)
print(count_partitions(5, 3))
print(count_partitions(30, 30))Notice how we checked this function: each base case by what it means, and the recursive case by the two groups. We never followed the 35 calls that count_partitions(5, 3) makes. To count with tree recursion, find one choice that splits the possibilities into groups, and let one recursive call count each group.
Listing every choice with one call per choice
Now suppose you want to list possibilities rather than count them: say, every 2-digit number whose digits are all 1 or 2. Those are 11, 12, 21 and 22, and two nested for loops, one per digit, print them. For 3-digit numbers you would need three nested loops. When the number of digits comes from the input, no fixed number of loops fits.
The function build(x, n) receives the number built so far and the count of digits still to add. When is 0, is finished and gets printed. Otherwise a for loop tries each digit from 1 to K and calls build with , which is with written on the end, and digits still to go. Each call makes one choice, the next digit, and trusts the recursive calls to list everything that can follow it.
Step through every 2-digit number made of 1s and 2s
In the first preset, frames for = 0, 1 and 11 are open at the deepest point. Each keeps its own d, so when the call for 1 returns, the first call moves on to the digit 2.
With digits to choose from and places there are numbers. The tree has one call for every partial number of each length from 0 to , but only of them, one for each length, are open at the same time:
Returning as soon as the number passes n
Often a call can tell that nothing further down its branch can be an answer, and return straight away without making its recursive calls. This problem needs that:
Count the numbers from 1 to whose decimal digits are all 0 or 1.
Constraints
Sample · Input
10
Output
2
In the sample, the numbers are 1 and 10. Checking every number up to would mean up to checks. A recursive search can instead build only numbers made of 0s and 1s: a call receives such a number and calls itself for and . Once , every number further down the branch is bigger still, so the call returns 0 at once. Otherwise it counts itself, plus whatever its two calls count. Returning early from a branch that can't contain an answer is called pruning.
def count_binary(x, n):
if x > n:
return 0
return 1 + count_binary(10 * x, n) + count_binary(10 * x + 1, n)
n = int(input())
print(count_binary(1, n))The search starts at 1, not 0, because count_binary(0, n) would call count_binary(0, n) again (Common mistakes, item 3). For , the search reaches the 512 numbers made of 0s and 1s up to , and each of them makes two calls, so there are calls instead of checks.
For practice, try this one. It works the same way, building numbers from the digits 3, 5 and 7 and stopping once a number passes . The new part is that a call also has to know which of the three digits its number already contains, so that it counts only numbers with all three:
Count the numbers from 1 to whose decimal digits include at least one 7, at least one 5 and at least one 3, and no other digit.
Constraints
- is an integer
Sample 1 · Input
575
Output
4
Sample 2 · Input
3600
Output
13
Sample 3 · Input
999999999
Output
26484
Give the function three more parameters, one True or False for each of the digits 3, 5 and 7, and pass True for the digit a call adds.
Common mistakes
Writing a base case that some inputs skip.
- Where it breaks
- With the base case
n == 0,fact(-1)moves away from 0, as the diagram's third preset shows. Python stops withRecursionError: maximum recursion depth exceeded; C++ crashes. - The fix
- Check that every chain of calls reaches a base case, and handle negative inputs before the recursive call.
Making the recursive call without returning its result.
- Where it breaks
- With the last line written as
n * fact(n - 1), withoutreturn, Python'sfact(1)returnsNone, sofact(2)computes2 * Noneand the program stops withTypeError: unsupported operand type(s) for *: 'int' and 'NoneType'. In C++, anintfunction that ends withoutreturnhas undefined behavior. - The fix
- Write
return n * fact(n - 1), so every path through the function returns a value.
A recursive call that does not change its input.
- Where it breaks
- In the 0s-and-1s search,
count_binary(0, n)callscount_binary(10 * 0, n), which is the same call again. Python stops withRecursionError; C++ crashes. - The fix
- Start from a number the calls grow, here
count_binary(1, n).
Recall Why does `fact(n)` finish for every $n \ge 0$?
Each call passes , so the inputs go down by one until they reach 0, where the base case returns 1 without calling again. After calls the chain ends.
Recall With `K = 2`, `build(0, 3)` lists every 3-digit number made of 1s and 2s. How many calls does it make, and how many `build` frames are open at most?
It makes calls and prints numbers, but at most four build frames are open at once, one each for numbers of 0, 1, 2 and 3 digits.
Key terms
| Term | Meaning |
|---|---|
| recursive function | A function that calls itself, directly or through another function. |
| base case | An input the function answers directly, without a recursive call: in fact. |
| recursive case | The part of the function that answers by calling itself on a smaller input. |
| recursive leap of faith | Assuming the call on the smaller input returns the right answer. |
| mutual recursion | Two or more functions that call each other. |
| depth | The number of frames a recursion has open at once. |
| stack overflow | The crash when a C++ program's frames fill the call stack. |
| tail call | A call whose result the function returns without further work. |
| tree recursion | Recursion in which one call can make two or more recursive calls. |
| partition | A way of writing a number as a sum of whole numbers, ignoring order: 5 = 3 + 1 + 1. |
| pruning | Returning early from a branch of the search that cannot contain an answer. |
