The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Conditionals and recursion Recursion
See also: Lists and Recursion, More Recursion, Infinite Recursion 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

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.

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.

What happens if we call this function like this:

void main ()
{
  countdown (3);
}

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

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

Last Update: 2005-12-05