6.1. Recursion

I mentioned in the last chapter that it is legal for one function to call another, and we have seen several examples of that. I neglected to mention that it is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

Note

The process of a function calling itself is called recursion, and such functions are said to be recursive.

For example, look at the following function:

void countdown (int n) {
  if (n == 0) {
    cout << "Blastoff!\n";
  } else {
    cout << n << endl;
    countdown (n - 1);
  }
}

The name of the function is countdown and it takes a single integer as a parameter. If the parameter is zero, it outputs the word “Blastoff.” Otherwise, it outputs the parameter and then calls a function named countdown —itself— passing n - 1 as an argument.

Watch how the countdown function works when we start with a value of 3.

Activity: CodeLens Recursion (recursion_codelens_1)

What happens if we call countdown function like this:

The execution of countdown begins with n = 3, and since n is not zero, it outputs the value 3, and then calls itself…

The execution of countdown begins with n = 2, and since n is not zero, it outputs the value 2, and then calls itself…

The execution of countdown begins with n = 1, and since n is not zero, it outputs the value 1, and then calls itself…

The execution of countdown begins with n = 0, and since n is zero, it outputs the word “Blastoff!” and then returns.

The countdown that got n = 1 returns.

The countdown that got n = 2 returns.

The countdown that got n = 3 returns.

And then you’re back in main (what a trip). So the total output looks like:

3
2
1
Blastoff!

As a second example, let’s look again at the functions new_line and three_line.

void new_line () {
  cout << endl;
}

void three_line () {
  new_line ();  new_line ();  new_line ();
}

Although these work, they would not be much help if I wanted to output 2 newlines, or 106. A better alternative would be

void repeat_lines (int n) {
  if (n > 0) {
    cout << endl;
    repeat_lines (n - 1);
  }
}

This program is similar to countdown; as long as n is greater than zero, it outputs one newline, and then calls itself to output n-1 additional newlines. Thus, the total number of newlines is 1 + (n - 1), which usually comes out to roughly n.

You can have a little bit of fun with recursion. Try this guessing game below!

You have attempted of activities on this page