Recursion

The next subject I want to talk about is recursion—did you just get a stomach ache? This may or may not be familiar to you. Recursion is simply a technique of solving a problem by induction—sorta. The basis of recursion is that many problems can be broken down into simpler problems of the same form, until at some point you can actually solve the problem. Then you assemble the large problem by combining the smaller problems. Sounds good, huh?

In computer programming, we usually use recursive algorithms for searching, sorting, and some mathematical operations. The premise is simple: You write a function that has the potential to call itself to solve the problem. Sound weird? Well, the key is that when a function calls itself, a new set of local variables are created on the stack, so it's really like another function is being called. The only things you have to worry about are that the function doesn't overflow the stack and that there is a terminal case at which the function terminates, whereby it can "unwind" the stack via multiple return()s. Let's jump into it with a standard example: the computation of a factorial.

The factorial of a number written as n! ("n bang") has the following meaning:

n! = n*(n-1)*(n-2)*(n-3)*...(2)*(1)

And 0! = 1! = 1,

Thus, 5! is 5*4*3*2*1.

Let's code this the normal way:

// assume integers
int Factorial(int n)
{
int sum = 1; // hold result

// accumulate product
while(n >= 1)
     {
     sum*=n;

     // decrement n
     n--;

     } // end while

// return the result
return(sum);

} // end Factorial

Looks pretty basic. If you send in a 0 or 1, you get 1. If you send it a 3, the following sequence occurs:

sum = sum * 3 = 1 * 3 = 3
sum = sum * 2 = 3 * 2 = 6
sum = sum * 1 = 6 * 1 = 6

Which is correct because 3! = 3*2*1.

Now here's the recursive version:

int Factorial_Rec(int n)
{
// test for terminal cases
if (n==0 || n==1) return(1);
else
   return(n*Factorial_Rec(n-1));

} // end Factorial_Rec

Tell me that isn't cool, my little leprechaun! So let's see what happens here when n is equal to 0 or 1. In these cases, the first if statement is TRUE, 1 is returned, and the function exits. But the cool stuff happens when n > 1. In this case, the else executes and the value returned is n times the function itself called with (n-1). This is recursion.

The state of the current function's variables remains on the stack, and the call is made to the function again as if it were another function with a new working set of variables. The code of the first return statement can't be completed until another call is made, and that return can't be completed until that call is made, and so on, until the terminal case is hit.

With that in mind, let's take a look at the n = 3 case with actual numbers replacing the variable n each iteration:

Now for the magic. The 1 is returned to the second call of Factorial_Rec() that looked like this:

return(2*Factorial_Rec(1));

This resolves to

return(2*1);

This then returns to the first call of Factorial_Rec() that looked like this:

return(3*Factorial_Rec(2));

This resolves to

return(3*2);

And presto, the function can finally return with 6—which is indeed 3! That's recursion. Now, you might ask which method is better—recursion or non-recursion? Obviously, the straightforward method is faster because there aren't any function calls or stack manipulation, but the recursive way is more elegant and better reflects the problem. This is the reason why we use recursion. Some algorithms are recursive in nature, trying to write non-recursive algorithms is tedious, and in the end they become recursive simulations that use stacks themselves! So use recursion if it's appropriate and simplifies the problem. Otherwise, use straight linear code.

For an example of recursion, take a look at DEMO11_2.CPP|EXE. It implements the factorial algorithm. Note how quickly factorial can overflow! See if the computer can beat your calculator's max factorial. Most calculators can compute up to 69! No lie.