If that were all there is to recursion, no one would ever use it.
However, recursion can be limited so it does not go out of control.
Controlled recursion can be a powerful programming technique.
When we discussed data structures, we remarked that programs and data
structures should aim to model the situation they deal with closely.
Some structures, both in real life and in computer memory, are made up
of many levels of detail, and the details are roughly the same at every
level. For example, a genealogical tree starts with an individual with
two parents, each of whom has two parents, each of whom... These sorts
of structure are called self-similar.
Since recursion employs functions that contain calls to themselves, in
effect creating multiple self-similar levels of detail, controlled
recursion is useful for dealing with self-similar problems.
Recursive functions can be controlled by making sure that there is a
safe way to exit them at some point in the chain of function calls. The
number of times recursion takes place is limited by making a decision
about whether the function calls itself or not. Simply put, somewhere
along the chain of function calls, the function makes the decision not
to call itself again, in a process nicknamed bottoming out. At
that point, the program begins popping addresses off the stack and
returning to the previous functions. Eventually, the very first
function in the chain terminates, and the program ends successfully.
A standard example of controlled recursion is the factorial function.
This is a mathematical function which is important in statistics. The
factorial function is defined to be the product (multiplication) of all
integers from 1 to the parameter of the function. (The factorial of 0 is 1.)
Here are some examples of the factorial function. These are not executable
C code examples, but pseudocode:
Formally, the factorial function is defined by two equations.
(Again, these are in pseudocode).
factorial(n) = n * factorial(n-1)
factorial(0) = 1
The first of these statements is recursive, because it defines
the value of factorial(n) in terms of factorial(n-1).
The second statement allows the function to "bottom out".
Here is a short code example that incorporates a factorial function.
#include <stdio.h>
int factorial (int n)
{
if (n == 0)
return 1;
else
return (n * factorial (n-1));
}
/* To shorten example, not using argp */
int main ()
{
printf ("%d\n", factorial(3));
return 0;
}
Let's follow the control flow in this program to see how controlled
recursion can work. The main function prints the value of
factorial(3). First, the factorial function is called
with the parameter 3. The function tests whether its parameter n
is zero. It is not, so it takes the else branch if the if
statement, which instructs it to return the value of
factorial(3-1). It therefore calls itself recursively with a
parameter of 2.
The new call checks whether its parameter is zero. It isn't (it's 2),
so it takes the else branch again, and tries to calculate 2
* factorial (1). In order to do so, it calls itself recursively with a
value of 2-1, or 1. The new call checks whether its parameter is zero.
It is actually 1, so it takes the else branch again and attempts
to calculate 1 * factorial (0). In order to do so, it calls
itself again with the parameter 0.
Again, the function checks whether its parameter is zero. This time it
is, so the function bottoms out. It takes the first branch of the
if statement and returns a value of 1. Now the previous function
call can also return a value, and so on, until the very first call to
factorial terminates, and the function returns a value of 6.
To sum up, the expression factorial(3) goes
through the following steps before finally being evaluated:
Note: Make sure that the test for whether to bottom out your
recursive function does not depend on a global variable.
Suppose you have a global variable called countdown, which your
recursive function decrements by 1 every time it is called. When
countdown equals zero, your recursive function bottoms out.
However, since other functions than the recursive function have access
to global variables, it is possible that another function might
independently change countdown in such a way that your recursive
function would never bottom out -- perhaps by continually incrementing it,
or perhaps even by setting it to a negative number.