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 . 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:
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:
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 , for any . 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 digits makes 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.
The call stack
To find the memory a recursive function uses, and to see why a very deep recursion crashes, we need to know what the computer does with a call that is waiting for another call.
When digit_sum(5072) calls digit_sum(507), the first call is not finished. It still has to add 2 to whatever comes back. The computer keeps it waiting in a frame, which holds the call's own variables and the place in the code where it will resume. The new call gets a frame of its own with its own n, so the two values of n, 5072 and 507, are kept apart.
The waiting frames form the call stack. It is a stack in the data-structure sense, where the last item added is the first removed: the newest call is on top and is the first to return. When it returns, its frame is removed, and the frame under it resumes with the returned value.
The number of frames on the stack at one moment is the depth of the recursion. digit_sum(5072) reaches a depth of 4, one frame for each digit.
The frames of digit_sum(5072)
The diagram below runs digit_sum(5072) one line at a time. A frame opens for each call, each with its own n, and the frames close in the reverse order. The preset One digit runs digit_sum(7), which the base case answers in the first call. The preset Base case n == 1 runs digit_sum(20) with the base case changed to n == 1, which breaks the function: 20 becomes 2 and then 0, and 0 never becomes 1, so the calls do not stop.
The limit on the depth
Every frame takes memory, so the depth cannot grow without limit. Python stops a program with a RecursionError once about 1,000 frames are on the stack. digit_sum stays far below that, since a number below has at most 18 digits. A function that makes one recursive call for each element of a list goes far past it: a list of 5,000 numbers needs 5,000 frames.
sys.setrecursionlimit(10000) raises the limit to 10,000 frames, and a submission whose recursion is deep calls it at the top of the program, after import sys. Python's documentation warns that a limit set too high can crash the interpreter, so raise it only as far as the input needs.
When the calls form one straight chain, as with one call for each element of a list, a loop does the same work without a stack.
Two recursive calls
digit_sum makes one recursive call, so its calls form a single chain. Many problems need two, such as the Tower of Hanoi.
There are three stacks, numbered 1, 2 and 3 from left to right. Stack 1 holds disks of different sizes, the largest at the bottom. Move every disk to stack 3. A move takes the top disk of one stack and puts it on top of another, and a disk may never sit on a smaller one.
The input is . Print the smallest number of moves , then lines with two integers and : a disk moves from stack to stack .
Constraints
Sample · Input
2
Output
3 1 2 1 3 2 3
The sample has two disks. The small disk moves to stack 2, out of the way, the large disk moves to stack 3, and the small disk follows it there. That is three moves.
Three disks take seven moves. In the table the disks are numbered by size, with disk 1 the smallest, and each stack is listed from its bottom disk to its top disk.
| Disk | Move | Stack 1 | Stack 2 | Stack 3 |
|---|---|---|---|---|
| start | 3 2 1 | |||
| 1 | stack 1 to stack 3 | 3 2 | 1 | |
| 2 | stack 1 to stack 2 | 3 | 2 | 1 |
| 1 | stack 3 to stack 2 | 3 | 2 1 | |
| 3 | stack 1 to stack 3 | 2 1 | 3 | |
| 1 | stack 2 to stack 1 | 1 | 2 | 3 |
| 2 | stack 2 to stack 3 | 1 | 3 2 | |
| 1 | stack 1 to stack 3 | 3 2 1 |
The table falls into three pieces. The first three moves take disks 1 and 2 from stack 1 to stack 2. The fourth move takes disk 3 from stack 1 to stack 3. The last three moves take disks 1 and 2 from stack 2 to stack 3. The first and the last piece are the two-disk puzzle again, played between other stacks. Disk 3 is never in their way, because any disk may be placed on it.
The same split works for any number of disks, because of where the largest disk can go. It cannot move at the start, because the other disks sit on top of it. It also cannot land on a smaller disk, so when it moves to the target stack, that stack must be empty and the smaller disks must all be on the spare stack, the one that is neither the start nor the target. So moving disks from one stack to another takes three steps:
- Move the top disks to the spare stack.
- Move the largest disk to the target stack.
- Move the disks from the spare stack onto it.
Steps 1 and 3 are the same problem with one disk fewer, so they are recursive calls. With one disk only step 2 is left, and that is the base case. You do not need to work out how the smaller disks move around inside steps 1 and 3: the recursive calls move them, just as digit_sum(507) added up the digits of 507 without our help.
The Tower of Hanoi in code
The function hanoi(n, source, target, spare, moves) moves the top disks from source to target and adds each move to the list moves. The program then prints the number of moves and the moves themselves.
def hanoi(n, source, target, spare, moves):
if n == 1:
moves.append((source, target))
return
hanoi(n - 1, source, spare, target, moves)
moves.append((source, target))
hanoi(n - 1, spare, target, source, moves)
n = int(input())
moves = []
hanoi(n, 1, 3, 2, moves)
print(len(moves))
print("\n".join(f"{a} {b}" for a, b in moves))The two recursive calls pass the stacks in different orders. The first call moves the disks to spare, so spare is that call's target and our target is its spare stack. The second call moves them from spare to target, with source as its spare stack. On the sample input 2, the program prints 3 and then the moves 1 2, 1 3 and 2 3.
Call trees
A function with two recursive calls does not make a chain of calls. If we draw each call under the call that made it, we get a tree, the call tree of the function.
The widget draws the call tree of hanoi for three disks, with the stacks named A, B and C in place of 1, 2 and 3. Each box shows how many disks a call moves and between which stacks. A call makes its own move after its first recursive call has returned and before its second one starts.
The Call stack panel never holds more than three calls, although the tree has seven. A call has returned before the call beside it starts, so the calls on the stack at one moment are one path from the top of the tree downwards. The depth of the recursion is the number of levels of the tree: 3 here, and for disks.
The tree also lets us count the calls. It has 1 call at the top, 2 on the next level and 4 on the last. With disks there are levels, and each level has twice as many calls as the one above it:
Every call makes exactly one move, so this is also the number of moves: 7 for 3 disks, and for the 16 disks the problem allows. The count roughly doubles with each disk added: 64 disks at one move a second would take seconds, about 585 billion years.
No solution has fewer moves. Before the largest disk first moves, the other disks must all be on the spare stack, and getting them there is the puzzle with disks. When the largest disk last moves, onto the target, they are all on the spare stack again and still have to be moved onto it, which is that puzzle again. So the fewest moves for disks are at least twice the fewest for disks, plus one. One disk needs 1 move, and doubling and adding one from there gives 3, 7, 15 and in general , the number of moves hanoi makes.
Time and memory of a recursive function
The call tree gives the cost of a recursive function. Write beside each call the work it does itself, not counting the work of the calls it makes. Every step of the program is done by exactly one call, so the running time is the sum of everything written in the tree.
When every call does about the same work, as in Hanoi, that sum is the number of calls multiplied by the work of one call. When the calls do different amounts, as in merge sort later in this chapter, it is easier to add up one level of the tree at a time. The memory is the largest depth multiplied by the size of one frame, plus whatever the calls store.
Calls and depth of the two functions
- `digit_sum` on a number with $d$ digits
calls, depth - Each call does one division, one remainder and one addition, so the time is . The stack takes memory.
- `hanoi` with $n$ disks
calls, depth - Each call records one move, so the time is . The stack takes memory, and the list of moves .
The stack counts toward the memory a recursive solution uses. A function that goes calls deep uses memory even when it creates no list of its own.
Memoization
The two recursive calls of hanoi do different work: one moves disks onto the spare stack and the other moves them off it. In the next function the two calls ask for some of the same answers.
The Fibonacci numbers start with and , and each later one is the sum of the two before it: . Given , return .
Constraints
Sample 1 · Input
n = 2
Output
1
Sample 2 · Input
n = 3
Output
2
Sample 3 · Input
n = 4
Output
3
The definition is a recursive function already. The base cases are and , and the recursive case adds two smaller calls:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)The widget draws its call tree for .
fib(5) makes 15 calls, and three of them are fib(2). Inside fib(4) it is worked out twice, once by fib(3) and once by fib(4) itself. Then fib(5) calls fib(3) a second time, and that call works out fib(2) a third time. In the whole tree fib(4) appears once, fib(3) twice, fib(2) three times and fib(1) five times, and those counts are Fibonacci numbers too. A call that is not a base case makes two more calls, so the number of calls follows almost the same rule as the Fibonacci numbers themselves:
The largest input the problem allows, , takes 2.7 million calls and passes. At the same function would make about calls, which at roughly simple operations a second is 400 seconds. All of those calls work out only 51 different values, fib(0) to fib(50).
The fix is to write each answer down the first time it is worked out, and look it up when it is asked for again. This is called memoization, and the table of stored answers is a memo. In Python the memo is a dictionary from to fib(n).
memo = {}
def fib(n):
if n < 2:
return n
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(30))
print(fib(50))A call looks in the memo first and works the answer out only when it is not there. Press the Use a memo button in the widget, and it makes 9 calls for fib(5): the second fib(3) and the second fib(2) return at once.
With the memo, each of the values from fib(2) to fib(n) is worked out once, and working one out makes two calls. Together with the first call, that is calls, 99 for . The number of calls drops from exponential in to about , and the price is memory for the memo.
A memo is safe when the arguments of a call decide its answer completely, as does here. Writing a recursive solution, noticing that it keeps asking for the same arguments, and storing the answers is also the first step of dynamic programming, which the DP lessons take further.
Reduce a question to a smaller one
Each function so far made its own input smaller: fewer digits, fewer disks, a smaller . The next function does the same, but its input describes a row of symbols far too large to build. The recursion answers a question about that row without building it, by turning it into the same question about a shorter row.
Build rows of 0s and 1s. Row 1 is 0. Each later row replaces every 0 of the row above with 01 and every 1 with 10, so row 2 is 01, row 3 is 0110 and row 4 is 01101001. Given and , return the th symbol of row , counting from 1.
Constraints
Sample 1 · Input
n = 1, k = 1
Output
0
Sample 2 · Input
n = 2, k = 1
Output
0
Sample 3 · Input
n = 2, k = 2
Output
1
Every row is twice as long as the row above it, so row 30 has symbols. Building the rows down to row 30 is too slow, and it is not needed, because the question is about a single symbol.
Each symbol of row was produced by one symbol of row , its parent. The parent at position 1 produced positions 1 and 2, the parent at position 2 produced positions 3 and 4, and in general the parent of position is at position , rounded down. A 0 becomes 01 and a 1 becomes 10, so in both cases the first symbol produced is the parent's own value and the second is the opposite value. The first lands on an odd position and the second on an even one.
So the symbol at position of row equals its parent when is odd, and is the opposite of its parent when is even. The parent's value is the same question one row higher, which is a recursive call. Row 1 is the single symbol 0, and that is the base case.
def kth_grammar(n, k):
if n == 1:
return 0
parent = kth_grammar(n - 1, (k + 1) // 2)
if k % 2 == 1:
return parent
return 1 - parent
print(kth_grammar(2, 2))
print(kth_grammar(4, 6))Each call moves up one row, so the answer for row 30 takes 30 calls and no row is ever built. The function runs in time on a stack that is frames deep.
Recursion on nested input
Some input is nested: a list can hold lists, and an expression can have smaller expressions inside its parentheses. A recursive function can follow that structure, with one call for each nested part.
An expression is one of: t (true), f (false), !(e) (NOT of the inner expression e), &(e1,e2,...) (AND of one or more inner expressions) or |(e1,e2,...) (OR of one or more inner expressions). Given a valid expression as a string, return its value.
Constraints
-
expression.length - Each character is one of
(,),&,|,!,t,fand,.
Sample 1 · Input
expression = "&(|(f))"
Output
false
Sample 2 · Input
expression = "|(f,f,f,t)"
Output
true
Sample 3 · Input
expression = "!(&(f,t))"
Output
true
Take the third sample, !(&(f,t)). The whole string is a NOT applied to the expression &(f,t), which is an AND applied to the expressions f and t. The AND is false, so the NOT is true.
Every part between the parentheses is again one of the five kinds of expression, so one function can evaluate any of them. The function has to report two things to its caller. The caller needs the value of the inner expression, and it also needs to know where that expression ended, because that is where it goes on reading: at a comma or at the closing parenthesis.
So parse(i) evaluates the expression that starts at index i, and returns its value together with the index just after its last character. It is defined inside parse_bool_expr so that it can read expression.
A t or an f is a base case, one character long. Any other expression starts with an operator and a (. The function steps over those two characters and then reads the inner expressions one at a time, each with a recursive call. After each one it finds either a comma, which it steps over, or the ), which ends the list. Then it combines the collected values according to the operator.
def parse_bool_expr(expression):
def parse(i):
c = expression[i]
if c == 't':
return True, i + 1
if c == 'f':
return False, i + 1
i += 2 # step over the operator and '('
values = []
while True:
value, i = parse(i)
values.append(value)
if expression[i] == ')':
break
i += 1 # step over ','
i += 1 # step over ')'
if c == '!':
return not values[0], i
if c == '&':
return all(values), i
return any(values), i
return parse(0)[0]
print(parse_bool_expr("!(&(f,t))"))
print(parse_bool_expr("|(f,f,f,t)"))
print(parse_bool_expr("&(|(f))"))On !(&(f,t)) the function is called four times, once for each expression in the string:
| Call starts at index | Expression it reads | Value | Index after the expression |
|---|---|---|---|
| 0 | !(&(f,t)) | true | 9 |
| 2 | &(f,t) | false | 8 |
| 4 | f | false | 5 |
| 6 | t | true | 7 |
Each character is read once, so the running time is for a string of length . The depth is one more than the number of parentheses open at the deepest point: f sits inside two open parentheses of !(&(f,t)), and the call that reads it is the third on the stack. The deepest valid input repeats !( and closes every one of them at the end, which takes three characters for each level, so a string of 20,000 characters can be nested 6,666 levels deep.
That is far past Python's limit of 1,000 frames, so a submission has to raise the limit with import sys and sys.setrecursionlimit(10000) at the top of the program. The listing above leaves this out because its three samples are shallow.
Practice: a game on a shrinking circle
In the K-th symbol, the answer for row came from the answer one row higher. The next problem is practice for the same idea: the winner in a circle of friends follows from the winner in a circle of .
friends sit in a circle, numbered 1 to clockwise. Starting from friend 1, count friends clockwise, including the one you start on; the last one counted leaves the circle. The next count starts from the friend just after the one who left. Repeat until one friend remains, and return that friend's number.
Constraints
Sample 1 · Input
n = 5, k = 2
Output
3
Sample 2 · Input
n = 6, k = 5
Output
1
In the first sample the friends leave in the order 2, 4, 1, 5, and friend 3 wins:
Playing the game out like this is one solution, and it is fast enough: at most 500 counts of at most 500 friends each, 250,000 steps. The recursive solution starts from one observation: after the first friend has left, what remains is the same game with friends, started at a different friend. Before you open the solution, try to work out how the winner of the smaller game gives the winner of the larger one.
The figure is a hint. It numbers the seats from 0, so friend 1 sits at seat 0, which makes the arithmetic simpler.
Solution: renumber the smaller circle
Number the seats from 0, and let the circle have friends. The first count starts at seat 0 and ends at seat ; the remainder is there for a count that goes around the circle more than once. That friend leaves, and the next count starts one seat later, at seat .
What is left is a game with friends that starts at our seat . Now give the remaining friends new seat numbers: 0 for the friend at that seat, and 1, 2 and so on around the circle. With the new numbers, this is the original game on a smaller circle. Seat of the smaller circle is seat of ours. In the figure, where and , the new seat 0 was seat 2, and the new seat 3 was seat .
So if the winner of the smaller game sits at its seat , the winner of our game sits at our seat . A circle of one friend has its winner at seat 0. Writing for the winner's seat in a circle of friends:
def winner(m, k):
# Seat, counted from 0, of the winner among m friends.
if m == 1:
return 0
return (winner(m - 1, k) + k) % m
def find_the_winner(n, k):
return winner(n, k) + 1
print(find_the_winner(5, 2))
print(find_the_winner(6, 5))For the winner's seat is 0, 0, 2, 0 and 2 in circles of 1 to 5 friends, and seat 2 is friend 3, as in the sample. The function makes calls and is frames deep, at most 500, which is under Python's limit of 1,000.
Common mistakes in recursive functions
A base case that the calls can step over.
- Where it breaks
- With the base case written as
n == 1,digit_sum(20)calls itself with 2 and then with 0, and 0 never becomes 1. The calls go on until Python raisesRecursionErroror the C++ program runs out of stack memory. - The fix
- Make the base case cover every input the calls can end on, here every
nbelow 10.
Creating the memo inside the function.
- Where it breaks
- A memo that is a local variable of
fibstarts out empty in every call, so no call ever finds a stored answer.fib(30)still makes 2,692,537 calls. - The fix
- Create the memo once, outside the function, so that all the calls share it.
Taking the parent of position as rounded down.
- Where it breaks
- For row 3, position 3, the parent becomes position 1 of row 2, and the function returns 0. Row 3 is
0110, so the right answer is 1. - The fix
- Positions 3 and 4 share the parent at position 2: use rounded down.
Recall Would a memo make `digit_sum` faster?
No. A memo saves work only when the same argument is asked for more than once. digit_sum(5072) calls itself with 507, 50 and 5, each once, so every lookup in the memo would miss. fib(5) gains from a memo because it asks for fib(2) three times.