Writing Recursive Programs in C

A factorial is an example of a problem that has a recursive solution, but also an iterative solution that is, ultimately, more direct and simple. In such cases, it is my firm belief that the iterative solution is one to use. However, let’s take a look at developing a recursive function for deriving a factorial.

First, a factorial can have a limitless number of cases – we can have 0!, 1!, 2!, 10!, and so on; note here that the ! simply means factorial, so first we should find a base or “trivial” case for which a solution is readily obtainable. Obviously, we should use 0!, where the answer is quite direct: it’s 1. Next, we must a means to solve more complex problems in terms of this simple solution, thereby reducing a complex problem to a simple problem that’s merely been scaled upwards.

Of course, this what problem solving is all about – reducing a complex system into a series of simple, clearly defined steps. Recursion is simply another means of doing this. With recursive logic, we are always trying to, in a sense, work backwards from a more complex case to the simple, base case, sort of like going from the tree to the seed.

Let’s take the factorial of 5, 5!, this would be 4! * 5, right? Likewise, we could say that 4! is really 4 * 3!, and 3! is really 3 * 2!. So we can see that the factorial of any number is itself multiplied by itself minus one. If we use n to represent a number, we get the formula

n ! = n * (n – 1)!

Thus, a factorial meets the two criteria for a recursive function: a base case whose solution is immediately apparent, and a clear chain from any other case back to the base case. In the formula n! = n * (n – 1)!, it is assumed that (n – 1)! is known; well, wait, how do we know what (n-1)! is? It’s simply ((n-1)!-1)! Likewise, ((n-1)!-1)! is really (((n-1)!-1)!-1)! So wait, does this go on forever? No! Because the buck stops at 0, that’s our base case, and 0! simply equals 1.

I think part of the problem for people to understand recursion in programming is that the popular notion of recursion is that it keeps going backwards forever.

This is getting obnoxious, I know, but the cool thing with a program is we don’t have to keep manually performing the recursion, we can have the computer do it for us. With the computer, we can always just assume that, as long as n-1! has been defined in a function, that it has already been solved for us, because functions are placed first in, first out on the stack.

A full explanation of the stack is beyond the scope of this post, but what should be understood is that the stack functions in a first-in, first-out manner, like a stack of plates by the sink. What this means is that if a function calls another function, which in turn calls another function, which in turn calls another function, the last function to be called will be the first to be executed, and the computer will work backwards from there. So all we have to do is make sure that when a function calls itself repeatedly, the last time it calls itself it reaches the base case, were a definite answer is returned.

It also helps if we think of a value-returning function as being a variable, that is, a logical stand-in for an associated mutable value.

#include <stdio.h>

#define BASECASE 1

int fact(int n);
int fact2(int n);
int fact3(int n);

int main(void){

printf(“3! = %d\n”, fact(3));
printf(“4! = %d\n”, fact(4));
printf(“5! = %d\n”, fact(5));

printf(“\n\n”);
fact3(6);
return 0;

}

int fact(int n){
if(n!=0){
return n * fact(n-1);
} else {
return 1;
}

}

//with the steps broken down
int fact2(int n){
int x;
if(n!=0){
x = fact2(x-1);
return (n*x);
} else {
return BASECASE;
}
}

//with the steps really broken down
int fact3(int n){
printf(“factorial function called with parameter %d\n”, n);

int x, y;
if(n!=0){
x = n – 1;
y = fact3(x);
printf(“Returning %d\n”, n * y);
return n * y;

} else {
printf(“Base case reached.\n”);
return BASECASE;
}

}

Next, we will look at the classic Towers of Hanoi problem. In the Towers of Hanoi problem, there are three pegs, labelled A, B, and C. On peg A we have stacked five disks, visually each disk is shown to have a larger diameter than the one above it, so the disk on top is the smallest and the disk on bottom is the largest, we want to move all of the disks, in order from smallest to largest, to peg C.

Simple enough, right? Just pick it up and drop it.

Well, the problem is we can only remove the topmost disk from a peg, and at any given point of time, the disks on each peg must be in order, so that the smaller disks are always on the larger disks. In fact, this is why we three pegs rather than two, and at any given point in time, one peg is the source, one peg is the goal, and one peg is the buffer between the two.

If you want a visual reference, see http://en.wikipedia.org/wiki/Towers_of_hanoi but, for me at least, it’s easier if I don’t have a picture in front of me.

Now, let’s cheat a little bit.

The cheat is that we already know the optimum solution: the number of steps to arrive at the solution is 2^n-1, with n being the number of disks. What does this tell us? Two things: one, with every disk we add, the number of extra steps doubles, and two, in the base case, we only have to move the disk once to arrive at the solution. Of course, this makes perfect sense, if there’s only one disk on the board, then the largest disk is the only disk, and we only have to move it to C.

Next, let’s use some tricks.

Our first trick is to think of the problem as a game. Seen as a game, the basic strategy is to make sure there are no disks on top of the largest disk, and no disks on peg C, and then we simply move the disk to C, where we remove it from play. Now, we don’t actually take the disk off of peg C, but as the disk is “out” we no longer have to think about it, and we can even mentally remove it, if we like. So, no matter how many disks we have “in play” at any given moment, the strategy is still the same – get all other disks off of the largest disk, and make sure no disk that is still in play is on peg C. Whenever we get the largest disk to C, it’s out of the game, and the next largest disk becomes the largest disk.

In other words, once we solve for n, n-1 becomes n. We don’t have to solve for n, we just have to get everything that isn’t n out of the way.

We can say that once the largest disk is at C, it’s “out”, we don’t have to worry about it, or think about it anymore, mentally we can just take it off the peg and throw it away, for all we care. Next, we see that all we have to do is make sure there are no disks on top of the largest disk, and no disks on C. How do we do that? Simple, we make sure that all of the disks except for the largest disk are neither on peg C nor the peg the largest disk is on.

Thus, while the description of the problem states that there are three pegs, A, B, C, we really ought to think that there are three pegs – the destination peg, which ultimately is always C, and the auxiliary and source pegs, which can be either A or B depending on the number of disks and where we are in executing the algorithm.

To sum up:

n = the largest disk still “in play”

n-1 = the set of all other disks

buffer / auxiliary peg = where we want n-1 to go

destination peg = where we want n to go

source peg = where n is

#include <stdio.h>
void towers(int n, char source, char buffer, char destination);

int main(void){

towers(4, 'A', 'B', 'C');

return 0;

}

void towers(int n, char source, char buffer, char destination){

if(n!=1){
     //move all but the largest disk to the buffer peg
        //note that the buffer peg becomes the destination peg
towers(n-1, source, destination, buffer);
 //move remaining largest disk from a to c
printf("move disk %d from peg %c to peg %c\n", n, source, destination);
 //now n-1 is the new n, so pass it back to the function to be moved to C
        //note the source is now the buffer, where the rest of the disks are
        //the original source peg will then be used as the buffer
        //the destination, of course, remains the same.
towers(n-1, buffer, source, destination);

} else {
printf("move disk %d from peg %c to peg %c\n", n, source, destination);
return;
}
}

If you can, please buy my book on C: http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s