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

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.

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

#include <iostream> #include <cmath> using namespace std; void countdown (int n) { if (n == 0) { cout << "Blastoff!" << endl; } else { cout << n << endl; countdown (n-1); } } int main () { countdown (3); return 0; }

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.

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

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; void guessTheNumber(int num) { cout << "Enter your guess!"; int guess; cin >> guess; cout << "Your guess " << guess << ". "; if (guess == num) { cout << "That's it!"; } else if (guess > num) { cout << "Too high! " << endl; guessTheNumber(num); } else { cout << "Too low! " << endl; guessTheNumber(num); } } int main() { srand((unsigned) time(0)); int randomNumber = (rand() % 10) + 1; guessTheNumber(randomNumber); }

Q-3: 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 "!"

Q-4: 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?
• 0
• 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.

You have attempted of activities on this page