A function can call any function the compiler knows about. That includes itself. A function that calls itself is called recursive, and writing one is called recursion.
Recursion adds no new piece of C++. Every statement in this lesson is one you have written before. What is new is a way of reading a call: as a job that is handed over, while the caller waits for it to come back.
Start with functions that call other functions. This program makes breakfast in three layers.
#include <iostream>
void spread_butter(int slice) {
std::cout << " butter on slice " << slice << "\n";
}
void make_toast(int slices) {
std::cout << " toasting " << slices << " slices\n";
for (int slice = 1; slice <= slices; ++slice) {
spread_butter(slice);
}
std::cout << " toast is ready\n";
}
void make_breakfast() {
int slices = 2;
std::cout << "breakfast starts\n";
make_toast(slices);
std::cout << "breakfast is ready\n";
}
int main() {
make_breakfast();
std::cout << "eat\n";
}
breakfast starts
toasting 2 slices
butter on slice 1
butter on slice 2
toast is ready
breakfast is ready
eatModule 6 said that a caller stops at a call and carries on when the called function has finished. Look at what that means when calls are inside calls. While spread_butter prints its line, three other functions have started and not finished. Each of them is waiting at the line of a call.
Here is every call in progress at the moment butter on slice 2 is printed.
| Call | What it is doing | Its variables |
|---|---|---|
main |
waiting at make_breakfast(); |
none |
make_breakfast |
waiting at make_toast(slices); |
slices is 2 |
make_toast |
waiting at spread_butter(slice); |
slices is 2, slice is 2 |
spread_butter |
running | slice is 2 |
This list is the call stack. It is called a stack because it behaves like a stack of plates: a new call goes on top, and only the call on top can finish and be taken off. The call that started last ends first.
Three things to notice.
make_toast still has its slice, and when spread_butter returns, the loop carries on from where it stopped.You can see the call stack in the lab. When you press Step through and step forward, the lab lists the calls in progress beside the program, each with its own variables, and marks every call except the running one as waiting. If you paste this program into the lab and step until butter on slice 2 appears, the list matches the table above. The first step of the lab asks you to read that list for another program.
A call puts a new entry on the stack, with new variables. Nothing in that rule says the called function must be a different one. This function calls itself.
#include <iostream>
void descend(int floor) {
if (floor == 0) {
std::cout << "ground floor\n";
return;
}
std::cout << "floor " << floor << "\n";
descend(floor - 1);
}
int main() {
descend(3);
std::cout << "outside\n";
}
floor 3
floor 2
floor 1
ground floor
outsideFollow it call by call.
main calls descend(3). Its parameter floor is 3. The condition is false, so it prints floor 3 and calls descend(2). Now it waits.descend(2) is a new call with its own floor, which is 2. It prints floor 2, calls descend(1) and waits.descend(1) prints floor 1, calls descend(0) and waits.descend(0) has a floor of 0. The condition is true: it prints ground floor and returns.descend(1) carries on after its call. There is nothing left in its body, so it ends. Then descend(2) ends, then descend(3), and main prints outside.The function was called four times, and at step 4 all four calls were in progress at once.
| Call | What it is doing | Its floor |
|---|---|---|
main |
waiting | none |
descend |
waiting | 3 |
descend |
waiting | 2 |
descend |
waiting | 1 |
descend |
running | 0 |
There is one definition of descend, and there are four variables named floor. That is the rule from module 6: every call gets its own parameters and local variables. Two calls of the same function share nothing but the text of the body.
This is not a loop. Nothing jumps back to the top of the body, and no variable is counted down: no statement ever changes a floor. Each call hands a smaller number to a new call.
Stepped through in the lab, this program shows the list of calls growing by one descend at a time, each with its own floor, and then shrinking again.
Every recursive function has two parts, and you can find both in descend.
descend it is a floor of 0.The function tests for the base case first. Then it is certain that the recursive case only runs when there is still something to hand on.
A recursive function can return a value too. This one adds up the whole numbers from 1 to n.
#include <iostream>
// Needs: n is 0 or more.
// Returns: 1 + 2 + ... + n, and 0 when n is 0.
int sum_to(int n) {
if (n == 0) {
return 0;
}
return n + sum_to(n - 1);
}
int main() {
std::cout << sum_to(4) << "\n";
std::cout << sum_to(100) << "\n";
}
10
5050Read the two parts as two sentences.
n is n plus the sum up to n - 1.Both sentences are true, and that is all you need to check. To write the recursive case, suppose the smaller call already works. If sum_to(3) gives 6, then sum_to(4) must give 4 + 6. You do not have to follow the calls all the way down each time, any more than you read the body of circle each time you draw one.
Two questions decide whether a recursion is sound.
In sum_to the recursive call gets n - 1. Starting from any n that is 0 or more, subtracting 1 again and again must arrive at 0. The contract says so in its first line: for a negative n the function promises nothing, because counting down from -1 never meets 0. The last section of this lesson shows what happens then.
A recursive call sits somewhere in the body. Statements before it run while the calls are being made, on the way down. Statements after it run when the calls come back, on the way up, and the calls come back in the opposite order.
These two functions print the digits of a number. They differ in one thing: which comes first, the print or the call.
#include <iostream>
void last_digit_first(int n) {
if (n < 10) {
std::cout << n << "\n";
return;
}
std::cout << n % 10 << "\n";
last_digit_first(n / 10);
}
void first_digit_first(int n) {
if (n < 10) {
std::cout << n << "\n";
return;
}
first_digit_first(n / 10);
std::cout << n % 10 << "\n";
}
int main() {
last_digit_first(472);
std::cout << "--\n";
first_digit_first(472);
}
2
7
4
--
4
7
2Both functions make the same three calls, with 472, then 47, then 4. n % 10 is the last digit of n, and n / 10 is n without it.
In last_digit_first each call prints its digit and then makes the next call. The call with 472 prints first, so the 2 comes first.
In first_digit_first each call makes the next call first and prints when that call has come back. So the call with 472 prints last.
| Call | Starts | Prints its digit |
|---|---|---|
first_digit_first(472) |
first | third: 2 |
first_digit_first(47) |
second | second: 7 |
first_digit_first(4) |
third | first: 4 |
While the call with 4 was running, the call with 472 was waiting on the stack. It kept its own n the whole time. When its turn came, n % 10 was still 2.
This is what the stack gives you that a loop over the digits does not. A loop that takes digits off with % 10 meets them last digit first. To print them in reading order it would have to store them somewhere. Here the waiting calls store them.
When a recursive function returns a value, you can check it on paper. Write each call on a line of its own, indented under the call that made it, until you reach a base case. Then fill in the returned values from the bottom up.
#include <iostream>
// Needs: n is 1 or more.
// Returns: how many times n can be halved, dropping fractions, before it is 1.
int halvings(int n) {
if (n == 1) {
return 0;
}
return 1 + halvings(n / 2);
}
int main() {
std::cout << halvings(20) << "\n";
std::cout << halvings(1) << "\n";
}
4
0Written out, the calls for halvings(20) look like this.
halvings(20) is 1 + halvings(10)
halvings(10) is 1 + halvings(5)
halvings(5) is 1 + halvings(2)
halvings(2) is 1 + halvings(1)
halvings(1) is 0 the base case
Going down, nothing can be added yet. Every line ends in a call whose value is not known. The first value that is known is the last line's.
Now go back up. Each call takes the value from the line below it and finishes its own addition.
| Call | Gets back | Returns |
|---|---|---|
halvings(1) |
nothing: it is the base case | 0 |
halvings(2) |
0 | 1 |
halvings(5) |
1 | 2 |
halvings(10) |
2 | 3 |
halvings(20) |
3 | 4 |
The returns happen in that order, the deepest call first. The call you wrote first returns last. At the deepest point five calls of halvings are in progress, four waiting and one running.
Stepping through shows the same thing. Each time a call ends, the lab says which call it was and what it returned, and that call leaves the list. Write the calls out on paper first, then step and compare. If the two differ, you have found something you misread.
Module 11 had a function with this name too, written with a loop, and it measured binary search: each look halves the range that is left. The two do not give the same number. Module 11's version went on halving until nothing was left, so it gives 5 for 20, the most elements a binary search of 20 can look at. This one stops when it reaches 1, one halving sooner, and gives 4.
So far each call made at most one more call, and the calls formed a chain. A function may call itself more than once. This one cuts a plank in half, and each half in half again, down to pieces of length 1. It prints each piece, indented by how many cuts it took to get there.
#include <iostream>
#include <string>
void cut(int length, const std::string& indent) {
std::cout << indent << length << "\n";
if (length == 1) {
return;
}
int left = length / 2;
cut(left, indent + " ");
cut(length - left, indent + " ");
}
int main() {
cut(4, "");
}
4
2
1
1
2
1
1The output is a picture of the calls: each line is one call, written under the call that made it. Every call that is not a base case makes two calls, so the calls branch. Such a picture is called a tree of calls. The first call is its root, and the base cases are its ends.
Read the order of the lines carefully.
cut(4) prints 4 and makes its first call, cut(2). It now waits.cut(2) prints 2, makes its first call cut(1), waits, then makes its second call cut(1), waits again, and ends.cut(4) make its second call.The whole of the first branch is finished before the second branch starts. The calls do not happen side by side: there is still one call stack, and one running call.
Count two different things in this tree.
A function that makes two calls for each call can do a great deal of work for a small input. Counting the calls, as you counted comparisons in module 11, tells you how much.
Any job a loop can do, a recursion can do, and the other way round. Here is sum_to from earlier in this lesson, next to the loop version that module 6 used.
#include <iostream>
int sum_to(int n) {
if (n == 0) {
return 0;
}
return n + sum_to(n - 1);
}
int sum_to_loop(int n) {
int total = 0;
for (int i = 1; i <= n; ++i) {
total += i;
}
return total;
}
int main() {
std::cout << sum_to(6) << " " << sum_to_loop(6) << "\n";
std::cout << sum_to(0) << " " << sum_to_loop(0) << "\n";
}
21 21
0 0The same parts are in both, in different places.
| The loop | The recursion | |
|---|---|---|
| Where it stops | the test i <= n becomes false |
the base case n == 0 |
| What moves it on | the update ++i |
the smaller argument n - 1 |
| Where the answer builds up | one variable, total, changed on every turn |
the return values, one addition in each call |
| Variables | two, for the whole job | one n for each call, never changed |
Which one should you write?
n times" or "do this for each element" is a loop. The loop is shorter to read, and it uses one set of variables however large n is. The recursion keeps one waiting call on the stack for every step, and each waiting call takes some memory.cut is five lines. Written with loops it would need a vector of the pieces still to be cut, managed by hand. That vector would be doing the work of the call stack.To turn a recursion that makes one call into a loop, find what changes from one call to the next. That becomes the variable the loop updates. The base case, turned round, becomes the loop's test.
A recursion stops because its calls reach the base case. Take the base case away and nothing stops it. Do not run this function.
void descend(int floor) {
std::cout << "floor " << floor << "\n";
descend(floor - 1);
}
descend(3) prints floor 3, floor 2, floor 1, floor 0, floor -1 and carries on. Each call waits for the next, so no call ever ends, and each waiting call keeps its place on the stack.
A loop that never ends runs until somebody stops it. A recursion that never ends is different: the memory set aside for the call stack is limited, and after many thousands of calls it is full. This is a stack overflow. The program is ended at once. In the lab you get a message that the program stopped while it was running, and the output shows only what was printed up to then. It is the second kind of error from module 7: the program compiles, and stops while running.
A base case that exists is not enough. The calls must reach it. This function has one, and can still step over it.
int count_pairs(int n) {
if (n == 0) {
return 0;
}
return 1 + count_pairs(n - 2);
}
count_pairs(6) makes calls with 6, 4, 2 and 0, and returns 3. count_pairs(5) makes calls with 5, 3, 1, -1, -3 and so on. The value 0 is never met, and the stack overflows.
There are two repairs, and a careful function has both.
if (n <= 0) in place of if (n == 0).// Needs: n is 0 or more and even. tells the caller which inputs are allowed, and tells you which inputs your base case must be reachable from.When a recursive program stops in this way, ask the two questions from earlier in this lesson, in order. Is there a base case? Does every recursive call move towards it, for every input the contract allows?