Node:Controlled recursion, Next:, Previous:The stack, Up:Recursion


Controlled recursion

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: 

factorial(3) == 1 * 2 * 3         ==   6
factorial(4) == 1 * 2 * 3 * 4     ==  24
factorial(3) == 1 * 2 * 3 * 4 * 5 == 120

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: 

factorial (3) == 3 * factorial(2)
              == 3 * (2 * factorial(1))
              == 3 * (2 * (1 * factorial(0)))
              == 3 * (2 * (1 * 1)))
              == 6

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.