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 << '\n';
    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.

Recursion
 1#include <iostream>
 2using std::cout;
 3
 4void countdown (int n) {
 5    if (n == 0) {
 6        cout << "Blastoff!\n";
 7    } else {
 8        cout << n << '\n';
 9        countdown (n-1);
10    }
11}
12
13int main () {
14    countdown (3);
15    return 0;
16}

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 << '\n';
}

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 << '\n';
    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!

Guessing Game.
 1#include <iostream>
 2#include <random>
 3
 4void guess_number(int num) {
 5    using std::cin;
 6    using std::cout;
 7    cout << "Enter your guess: ";
 8    int guess;
 9    cin >> guess;
10    if (guess == num) {
11        cout << "That's it!";
12    }
13    else if (guess > num) {
14        cout << "Too high! ";
15        guess_number(num);
16    }
17    else {
18        cout << "Too low! ";
19        guess_number(num);
20    }
21}
22
23int main() {
24    // make a random number generator
25    std::random_device r;
26    std::default_random_engine eng(r());
27
28    int random_number = std::uniform_int_distribution<int> {1, 100} (eng);
29    guess_number(random_number);
30}

Q1

What will print?

#include <iostream>
using namespace std;

void exclamation_point(int n) {
  if (n > 0) {
    cout << '!';
    exclamation_point (n-1);
  }
}

int main () {
  exclamation_point(3);
}

Q2

What will print?

#include <iostream>
using namespace std;

void exclamation_point(int n) {
  if (n > 0) {
    cout << '!';
    exclamation_point (n-1);
  }
}

int main () {
  exclamation_point(0);
}

Q3

A function that calls itself is said to be .