Skip to main content

How To Think Like a Computer Scientist C++ Edition The Pretext Interactive Version

Section 4.7 Recursion

What mentioned in the last chapter is 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 4.7.1.

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!" << endl;
  }
  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.

Activity 4.7.1.

Watch how the countdown function works when we start with a value of 3.
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 get n = 1 returns.
The countdown that get n = 2 returns.
The countdown that get 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 newLine and threeLine.
void newLine() {
  cout << endl;
}

void threeLine() {
  newLine();
  newLine();
  newLine();
}
Although these work, they would not be much help if I wanted to output 2 newlines, or 4 newlines. A better alternative would be
void nLines(int n) {
  if (n > 0) {
    cout << endl;
    nLines (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.
Listing 4.7.1. You can have a little bit of fun with recursion. Try this guessing game below!

Checkpoint 4.7.1.

What will print?
#include <iostream>
using namespace std;

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

int main() {
  exclamationPoint(3);
}
  • The function keeps executing while n is greater than 0.
  • !!
  • The function keeps executing while n is greater than 0.
  • !!!
  • Correct! First, the program enters the if statement within exclamationPoint because n is greater than 0. Then the function prints a "!" and calls itself again, but with n-1, which is 2. This repeats until n is 0, which is when the program exits the function.
  • !!!!
  • The function keeps executing while n is greater than 0. Therefore, when n is 0, it will not print a "!"

Checkpoint 4.7.2.

What will print?
#include <iostream>
using namespace std;

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

int main() {
  exclamationPoint(0);
}
  • !!
  • If we start at zero, will the function ever call itself?
  • If we start at zero, will the function ever call itself?
  • The only output statement in this program prints a "!", therefore "0" would never print.
  • Nothing prints.
  • Correct! The program never enters the "if" statement within the function because n is never greater than 0.

Checkpoint 4.7.3.

You have attempted 1 of 4 activities on this page.