In most modern languages, there are two fundamental approaches to repeating an action: either iteration, in which an action is placed inside a special-purpose structure which causes the action to be repeated, or recursion, in which a general-purpose function calls itself (or another function which in turn calls the earlier function). Which is to be used depends on the nature of the problem at hand, and to a great degree, the language being used. Some languages, especially Lisp and the various functional languages, strongly favor recursion; but most other languages, including C++, focus almost entirely on iteration.
As a result, novice C++ programmers are often given little if any experience with recursion, which tends to lead to it being overlooked even for problems where it is well suited. Also, recursive design takes a very different view of what it means to repeat something, and the approach can seem alien to programmers more familir with iteration. Finally, because it is based on function calls, recursion generally takes more memory and time than the equivalent iteration, and while there are ways for a compiler to optimize away this overhead for some types of recursion (specifically tail calls, where the recursive call is the last step in the function), few C++ compilers do any tail call optimization. As a result, recursion is poorly understood by many C++ programmers.
This is unfortunate, as in some ways recursion is the simpler of the two approaches to looping. It does not require any additional language constructs other than conditionals and function calls, and once you are familiar with the general approach, it can seem as natural as iteration.
The key idea behind a recursive program is having a function which calls itself. A simple example of this would be:
void infinite_stars()
{
std::cout << '*';
infinite_stars();
}
This is a function which, when called, prints out asterisks until the stack is exhausted, or until the user interrupts the program. It is equivalent to the iterative function:
void infinite_stars()
{
while (true)
{
std::cout << '*';
}
}
... except that the call stack gets used up in the function calls. For those unfamiliar with it, the call stack is a stack supported by the computer hardware which provides the space in memory where local function variables are stored; every time you calll a function, the stack is advanced by enough space hold everything used by the function. This space is called the functions environment, or activation record. When the function exits, the top of the stack is moved back to the level of the previous function's activation record. Because there is an activation record for each new call of the function, a function which calls itself can have multiple activation records, which means that the calls do not interfere with each other.
Because this function uses a tail call - a function call which is the last action in the function - the compiler could make it so that the activation record gets re-used, such that the stack would never get used up. I'll explain more about this later, but for now, be aware that this is something C++ compilers could do, but generally don't except as a option or switch.
Now, an infinite loop like this isn't usually very helpful, so in order to make a practical recursive function, you would want to have an exit condition, just as you do with an iteration. Let's modify our function so that it repeats a fixed number of times, given by the parameter n:
void stars(int n)
{
if (n <= 0)
{
return;
}
else
{
std::cout << '*';
stars (n - 1);
}
}
This is equivalent to:
void stars(int n)
{
for (int i = 0; i < n; i++)
{
std::cout << '*';
}
}
Now you should notice three things about this function: first, that it checks for the exit condition before it performs the recursive call; second, that each of the successive calls has a different value of n; and third, that each successive call's n is one less than the call before it. This means that, as the calls progress, it counts down to zero, which is the exit condition. If we look at the calls as they appear on the call stack, they would look something like this:
-> stars(5)
-> stars(5) -> stars (4)
-> stars(5) -> stars (4) -> stars(3)
-> stars(5) -> stars (4) -> stars(3) -> stars(2)
-> stars(5) -> stars (4) -> stars(3) -> stars(2) ->stars(1)
-> stars(5) -> stars (4) -> stars(3) -> stars(2) ->stars(1) -> stars(0)
-> stars(5) -> stars (4) -> stars(3) -> stars(2) <-stars(1)
-> stars(5) -> stars (4) -> stars(3) <- stars(2)
-> stars(5) -> stars (4) <- stars(3)
-> stars(5) <- stars (4)
<- stars(5)
Now, you may ask yourself: why bother? The iterative version seems simpler, and more familiar, so why mess around with this when it is less efficient? Well, the answer is, because there are some problems that are a lot easier to solve with recursion than with iteration. For example, imagine having to count all the different combinations of coins which could make up a given value in dollars and cents. To solve it recursively is fairly simple:
// simple recursive method
int count(int sum, int *coins)
{
if (!*coins || sum < 0)
{
return 0;
}
else if (!sum)
{
return 1;
}
else
{
return count(sum - *coins, coins) + count(sum, coins + 1);
}
}
but to solve it with an iterative approach, you would need to have an explicit stack data structure, in order to keep track of where you are, which is harder to understand. While it can be proven that recursion and iteration are equivalent - that is to say, anything that can be done with iteration can be done with recursion, and vice versa - there are some problems which are easier to solve recursively.
Now, I had said earlier that in some cases, recursive calls can be optimized so that the activation record is re-used. How this works is, the compiler would simply replace the recursive tail call with a goto or jump, and replace the old values of the arguments with the new ones. In C++, this would mean turning the recursive version of stars() into something like this:
void stars(int n)
{
loop:
if (n <= 0)
{
return;
}
else
{
std::cout << '*';
n--;
goto loop;
}
}
Of course, the programmer wouldn't see this; it would be in the code that the compiler generates, not something that you would actually write out.
