"Old sages by the figure of the snake Encircled thus did oft expression make Of annual revolutions; and of things, Which wheele about in everlasting rings; There ending, where they first of all begun." -George Wither, A Collection of Emblemes, Ancient and Moderne
Over the years, a number of advanced and powerful programming techniques have become available to hobbyists , small systems programmers and small businesses. Many have only recently become practical for application in small systems as the speed and capacity of the "low-end" computers increased to match that of the giant machines they were originally developed on so many years ago.
One of these techniques is called recursion. Simply put, recursion is when a program or function calls or executes itself in its normal course of operation. If visualized physically, recursion might resemble a snake that is swallowing itself, or the well-known , endless, and strangely multidimensional "klein bottle".
At first glance, the concept of recursion seems like a silly contradiction that is so complex as to be impossible for the average person to understand. But, a careful look at what recursion is, and what it can do will reveal that it is not only simple and understandable, but often offers an elegant, work-saving solution for many otherwise complicated and difficult problems. In fact, for some situations, it is the only practical solution to the often complex and difficult tasks that today's programmers frequently face.
The Klein bottle is a surface folding back on itself endlessly. Recursion really is a lot like this... it's as complex, or as simple as you care to make it....
So where do we start?
First, we will take a short look at a simple function that uses recursion, then we will expand on that knowlege and use it in a few simple programs that actually do some useful things.....
What is the basic idea here?
The simplest form of a recursive function call will be something like the code below.... This code should compile and run, but will eventually cause an error when the operating system runs out of memory because the function calls never end.
CODE BEGINS
#include<stdlib.h>
void myfun(void);
void main(void)
{
myfun();
}
void myfun(void)
{
myfun();
}
CODE ENDS
The obvious problem with this program is that it tries to recurse forever because it has no means of limiting the recursion. An easy way of limiting recursion is by means of checking the condition of passed parameters.
Coding the real deal.....
Below, is a program that recurses a number of times. To keep the computer from running out of memory , the number of iterations has been limited by using a while loop to make the recursive call.
Before it calls itself, the message "Running Instance:" appears, followed by a number. After the function call, the message "Returning from Instance:" followed by the number of the instance appears. After a certain number of instances the recursive call ends, and all of the function calls exit, and program flow returns to the main body of the program .
Type this program in and run it and then count the number of times the function is actually called by counting the number of times the "Running Instance:" message appears.
You will note that the line: while(b<10)myfun(b); suggests that it will happen ten times, but the actual number of times the recursion occurs is significantly greater than ten. In fact, it recurses 511 times, for a total of 512 function calls! As though to make matters worse, the value of the variable "b" did not reflect the actual number of times the program recursed. Why should that happen ? What do we need to do to make this program behave "normally" ?
.
CODE BEGINS
#include<stdio.h>
#include<stdlib.h>
void myfun(int);
int main(void)
{
int a=1;
myfun(a);
printf("done\n");
return(0);
}
void myfun(int b)
{
printf("Running Instance: %d\n",b);
while(b<10)
{
b++;
myfun(b);
}
printf("Returning from instance: %d\n",b);
}
CODE ENDS
Why is this program behaving so oddly ?
The thing that is important to note here is the value of the variable "b" when the functions begin to exit.
Even though "b" reached a value of 10 in the last instance of the function calling itself, it did not return its value to the previous instances. This means that after the last instance exited with a value of 10, when the function exited, the previous instance will have a uniqe variable "b" with a value of "9", and the one before that will have a "b" with a value of "8", and so on, with each copy of the function calling itself recursively until they all have satisfied the condition of the while loop independently. In order for the recursoin to end when one instance reaches "10" for a value of "b", myfun should be modified to return the value of the variable "b" so that the previous instance's condition for exiting the while loop can be satisfied.
This kind of behavior is the key to recursion. If you can develop a fundamental grasp of the fact that each instance of the function call is a separate entity, you can use it to make programs that do some very useful and amazing things.
Time for something a bit more sane....
Below is the code for the same program as above "corrected" to assure the recursion ends at the tenth instance. Note that the only change was to modify the recursive function to return the value of the counter used so that all instances of it get the right value for "b". This program recurses 9 times, with a total of 10 function calls made to "myfun".
CODE BEGINS
#include<stdio.h>
#include<stdlib.h>
int myfun(int);
int main(void)
{
int a=1;
myfun(a);
printf("done\n");
return(0);
}
int myfun(int b)
{
printf("Running Instance: %d\n",b);
while(b<10)
{
b++;
b=myfun(b);
}
printf("Returning from instance: %d\n",b);
return(b);
}
CODE ENDS
Pitfalls and caveats.... what you really need to know....
Recursion brings a mixed blessing. It can make simple work of otherwise complex and enormously iterative tasks. It can also be a nightmare that brings the system to its knees by hogging huge amounts of memory.
The down side of recursion starts to sink in when you realize that the functioning of the code is not always immediately apparent on inspection, so another programmer who is unfamiliar with your code might find it difficult to work with.
Debugging recursive routines can be maddeningly difficult. It can take great patience and skill to have success fixing broken recursive code.
Recursive programs tend to have very "tight" code in that making modifications to an existing design can prove difficult, even impossible. In fact, it's often easier to rewrite a recursive function than it is to patch in changes.
Lastly, perhaps most importantly, recursion can be a resource hog, using up precious memory resources rather quickly. For systems that have scant memory resources (Such as DOS in real mode), the programmer may elect to avoid using recursion unless there is no other choice.
So when is recursion the "best" tool for the job ?
I can't really tell you how to balance all of this into a clear-cut answer, but good judgment , careful design and planning are probably going to be your best guides for these decisions.
Lots of people will share opinions on this. As a general rule, recursion becomes a possible alternative when memory useage is not considered to be a problem. Recursion becomes the preferred choice if using it results in a significant reduction in code, complexity, and/or a significant improvement in performance. Also, recursion becomes much more desirable in instances wherin production time is reduced.
A few real world examples.....
Statistical functions, fractal landscapes, directory listings, state machines, and computer animation are just a few examples of good applications for recursion. The list goes on, but I 'm confident that you now have some ideas as to when recursion is appropriate, and when it is not.
Enough Said......
Now that you have reached this point in this article, you have completed the five-cent tour of the advanced programming technique of recursion. Experiment with this tool, and have fun with it. Use it to explore your programming abilities and to create new, and fun things.
Below, are the "useful" example programs that I was raving about earlier., These programs work, and have seen some use by quite a few programmers if the number of downloads from my ftp site are any testimony of their usefulness. Experiment with these programs and have some fun taking them apart so you can get a better idea of how recursion works.
You can download the source for these sample programs at: http://www.night-flyer.com/index.htm
In closing, I would like to thank Gambit for allowing me to use a bit of his code as an example of recursion. I would also like to thank my dear friend Cruinne for providing several really fantastic images of various Ouroborouses (ourobi??)... well, anyway, thanks for the snakes...
Glen E. Gardner, Jr. (Aegis)
COMBINATION.TXT by Benn Bollay (Gambit)
Quite some time ago Gambit came up with a very clever solution to the problem of finding combinations via recursion , and wrote a function that applied the solution in a rather elegant fashion. I've always viewed this code as a good example of simplifying code by means of using recursion, so it has been included here.
The code for it appears in the file "combination.txt" ,below in its orginal form.
COMBINATION.TXT BEGINS
Copyright 1998, Benn Bollay (bbollay@polymail.calpoly.edu)
Usage of this routine is granted for whatever purpose desired on the sole condition that
the user emails Benn Bollay and tells him what they are using it for :)
This little algorythm outputs all possible combinations (order matters, might be wrong term) of 'num' values located in an array.
void order(int array[], int num) {
int n = array[0];
do {
output(array);
if(num > 2)
order(array + 1, num - 1);
rotate(array, num - 1);
} while (ints[0] != n);
}
The rotate takes the int at the bottom of the array, and brings it to the [0] position, rotating all the other ints down one level in the process.
COMBINATION.TXT ENDS
PRIME2.C by Glen E. Gardner, Jr. (Aegis)
Generating prime numbers is of interest to mathematicians, and cryptography fans.
There are a number of good prime number generators available, but many of them are iterative and sometimes a bit awkward. Some time ago , I wrote a simple prime number generator that uses tail recursion. The code for that program appears below.
BEGIN CODE
/* Program PRIME2.C A Recursive Prime Number Generator */
/* Written and Edited by Glen E. Gardner, Jr. 1/26/98 */
/* */
/* Checks for primes by assuming all numbers are divisible by "1" and itself, */
/* then divides the number being tested by all values from "1" to the number under */
/* scrutiny, and testing for a remainder. Tail recursion is used to simplify the code */
#include<math.h>
#include<stdio.h>
int CheckPrime(int,double,double);
int main(int argc,char *argv[])
{
int temp;
double num1,num2;
num2=0;
if(argc<2)
{
printf("USAGE: PRIME <MAXPRIME>\n");
return(0);
}
CheckPrime(atoi(argv[1]),num1,num2);
return(0);
}
int CheckPrime(int num,double num1,double num2)
{
int temp;
if(modf((num2/(num1+1)),&temp)!=0){printf("%f\n",num2);}
if(num2<num){num=CheckPrime(num,1,num2+1);}
return(num);
}
END CODE
DIRTREE.C by Glen E. Gardner, Jr. (Aegis)
In all likelihood, the best example of an application wherin recursion is generally accepted as being superior, is in the traversal of trees. The manipulation of binary trees becomes so horribly iterative and complex without the use of recursion that most programmers will agree that the use of recursion is, without doubt, the best possible solution for the task.
Below is source code for a program that I have written called "DIRTREE.C" It uses recursion to traverse all directories in its path in order to create a listing of all of the files and directories in that path.
To do this iteratively, would almost certainly require a lot more code, and result in a program that is much more complicated than this one.
Unfortunately, this program was written in a rather inelegant style, because it was originally intended to be a "quick solution" to a portion of a small project I was working on. The code definitely works, so is presented here to illustrate the point that recursion is sometimes "better".
I currently use a modified version of this program to automatically index downloadables on my web site.
CODE BEGINS
/* DIRTREE.C V 1.0 by Glen E. Gardner, Jr. */
/* A recursive directory tree traversal that finds the path and names */
/* for all files in the specified path. */
/* this program was written and compiled using Borland C++ 5.0 on */
/* Microsoft Windows NT 4.0 */
/* The program was written with no MS API function calls, for as much */
/* OS independence as was practical. */
/* It should compile and run on DOS, Win 3.X , Win 95/98 and Win NT. */
/* This program was written in ansi C as much as was possible, UNIX users might */
/* find this program easy to port. */
#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
#include <dir.h>
#include <string.h>
int scandir(char *,char *);
int getsize(char *);
void doit(char *);
int scanstring(char *,char *);
void main(int argc,char *argv[])
{
chdir(argv[1]);
if (argc != 2)
{
printf("usage: DIRTREE <PATH>\n");
exit(1);
}
doit(".");
exit(0);
}
int getsize(char *dirname)
{/* finds and returns the size of the directory entry (in bytes) */
DIR *dir;
struct dirent *ent;
int size=0;
if ((dir = opendir(dirname)) == NULL)
{
perror("Unable to open directory");
return(NULL);
}
while ((ent = readdir(dir)) != NULL);
rewinddir(dir);
while ((ent = readdir(dir)) != NULL)size=size+sizeof(ent->d_name)+1;
if (closedir(dir) != 0)
perror("Unable to close directory");
return(size);
}
int scandir(char *dirname,char *entries)
{/* scan the directory and store the entries in a buffer */
DIR *dir;
struct dirent *ent;
int count=1;
char name[256];
if ((dir = opendir(dirname)) == NULL)
{
perror("Unable to open directory");
return(0);
}
while ((ent = readdir(dir)) != NULL)count++;
rewinddir(dir);
while ((ent = readdir(dir)) != NULL)
{
strcpy(name,ent->d_name);
sprintf(entries,"%s",name);
entries=entries+strlen(name)+1;
count++;
}
if (closedir(dir) != 0)
perror("Unable to close directory");
return(count);
}
void doit(char *dirname)
{/* scan the buffer and recursively enter any directories found */
int size;
char *entries;
char name[256];
char Path[256];
char *path;
char oldpath[256];
char old[256]="none";
FILE *filein;
path=Path;
size=getsize(dirname);
entries=(char *)malloc(size);
scandir(dirname,entries);
getcwd(Path,256);
strcpy(old,Path);
while(scanstring(name,entries)!=EOF)
{
/* store the path for use later */
getcwd(Path,256);
if((strcmp(name,"."))&&(strcmp(name,"..")))
{
/* this is where the valid path variable can be found */
if(!strcmp(Path,old))printf("PATH: %s\n",Path);
strcpy(oldpath,Path);
/* add the next entry to the path for testing */
strcat(Path,"\\");
strcat(Path,name);
/* see if the entry is a file */
/* here is where the valid filename associated with the path can be found */
if((filein=fopen(Path,"r"))!=0)
{
printf("NAME: %s\n",name);
fclose(filein);
}
else
{
if(chdir(Path)==0)
{/* if the entry is a valid directory, go there */
getcwd(path,256);
/* start the recursive traversal */
doit(".");
/* restore the path */
strcpy(Path,oldpath);
chdir(Path);
getcwd(path,256);
}
}
/* set the sentinel variable for state changes */
strcpy(old,Path);
strcpy(Path,oldpath);
chdir(Path);
getcwd(path,256);
}
entries=entries+strlen(name)+1;
}
return;
}
int scanstring(char *string,char *buffer)
{
int i;
int size;
char *temp;
size=0;
temp=buffer;
while(*buffer!=NULL)
{
size++;
buffer++;
}
buffer=temp;
for(i=0;i<=size;i++)
{
*string=*buffer;
buffer++;
string++;
}
*string=*buffer;
buffer=buffer-2;
if(*buffer==NULL)return(EOF);
return(size);
}
CODE ENDS
This page is Copyright © 1999 By C Scene. All Rights Reserved