Recursion

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.

Calls that wait

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
eat

Module 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.

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.

• Only the call on top is running. Every call below it is waiting for the one above.
• A waiting call keeps its variables. make_toast still has its slice, and when spread_butter returns, the loop carries on from where it stopped.
• When a call ends, it leaves the stack and its variables are gone. The call below it carries on at the statement after the call.

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 function that calls itself

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
outside

Follow it call by call.

1. 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.
2. descend(2) is a new call with its own floor, which is 2. It prints floor 2, calls descend(1) and waits.
3. descend(1) prints floor 1, calls descend(0) and waits.
4. descend(0) has a floor of 0. The condition is true: it prints ground floor and returns.
5. 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.

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.

The case that stops

Every recursive function has two parts, and you can find both in descend.

• The base case is the input that is small enough to answer without another call. For descend it is a floor of 0.
• The recursive case is everything else. It does one small part of the job and gives the rest, which is a smaller version of the same job, to a call of the same function.

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
5050

Read the two parts as two sentences.

• Base case: the sum of no numbers is 0.
• Recursive case: the sum up to 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.

1. Is there a base case that answers without calling the function again?
2. Does every recursive call get an input that is nearer to the base case?

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.

Before the call, and after it

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
2

Both 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.

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.

Writing out the calls

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
0

Written 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.

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.

Two calls each

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
    1

The 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.
• That cut(2) prints 2, makes its first call cut(1), waits, then makes its second call cut(1), waits again, and ends.
• Only now does 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.

• How many calls in all? One of length 4, two of length 2, four of length 1: seven. A plank of 8 gives 15 calls, and a plank of 1024 gives 2047. Each extra level doubles the number of calls in that level.
• How many calls in progress at once? Never more than three: a 4, a 2 and a 1. The stack holds one path from the root to the running call, not the whole 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.

A loop or a recursion?

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 0

The same parts are in both, in different places.

Which one should you write?

• A job that is "do this 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.
• A job that contains smaller copies of itself is a recursion, above all when there is more than one copy. 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.

When it never stops

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.

• Make the base case wide enough to catch everything at or beyond the end: if (n <= 0) in place of if (n == 0).
• Write the contract, as in module 7. // 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?