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

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!