Recursion in Computer Science: Part 1

• Download source code - 1.31 KB
• Download compiled program - 22 KB

Abstract

Recursion in programming in contrast to "recur" (in Oxford Advanced Learner's Dictionary) means something that happens a number of times. It is a situation where by a function call (in modular programming), a method (in OBJ programming) recalls itself a number of times (or infinitely) probably intentionally, but mostly unintentional due to algorithmic errors. But, over the years, recursion has become very useful in complex situations (such as programming and mathematical calculations) and deserves a good explanation on its importance and applications.

Note: This article will not elaborate extensively on the subject, it will only highlight its importance and applications. I believe people learn faster this way (at least I do) than when overwhelming people with big grammars and formulas. If you need generalized texts on it (recursion), see Wikipedia.

This series will introduce you to recursion and show some of its useful applications. For this first part, I discuss file/folder iteration using recursion. I will skip all mathematical stuff and go straight to the programming aspects. Try to read it till the end, and remember to rate the article, it will greatly influence the next part.

Introduction

First, let me apologize if my articles, jokes, and code hurt you (the developer's community). I'm not an English-man and my mother tongue is Yoruba (a South-Western Nigerian language). I decided to write this note to share a fraction of my God given ideas. If I must say, writing this article is strenuous than programming itself. I decided to write this article after I developed a file manager for my phone using the Symbian C API (Application Programming Interface).

[A file manager is a Windows Explorer like application. You must not PM me for the full source!]

What is recursion? Recursion is the process a procedure goes through when one step of the procedure involves rerunning the entire same procedure. Most people misinterpret the concept of recursion with that of a loop. But here, I want you to see recursion as a spring or a "yoyo" stretching to a limit and later returning back to its initial state/size "after stretching". A loop on the other hand should be pictured as a ceiling fan, spinning "in one direction" for some time (or forever till something interrupts). In programming however, these two are indispensable, with the loop being the more used of the two.

<See recursion versus loops in the next chapter.>

To be more specific, recursion in computer science and mathematics is when a function is defined and the same function is applied within the same function. Recursion simply means for something to happen over and over again spontaneously or mistakenly (due to errors); e.g., LAME as a recursive acronym: LAME is not An Mp3 Encoder. See?

Recursion! If you still don't see it; see "Recursion".

Recursion is mostly employed to breakdown large and complex operations into smaller and simple steps "engineered" to accomplish the same task if a more direct and complex approach is used (more like "divide and conquer" approach). To use recursion satisfactorily well, one most first understand its greatness, and this is what this part is designed for. If you are wondering how to solve a factorial using programming, or some other mathematical problems, please look out for other coming parts.

Note: The sample code with this write-up is clear, heavily commented, and self-explanatory. But if you still find it unclear, PM me: gx_306@yahoo.com for a clearer explanation. :S. And for those who rated the article low due to bad text formatting, well, I hope you changed your mind now as I have rewritten the whole thing.

"In order to understand recursion, one must first understand recursion!"

The sample code

The sample program / code accompanying this article uses a recursive process to search and print out all files (hidden or not), starting from a root directory passed to it as a parameter to the last sub-directory along the directory path. The entire code is written in the C programming language. Lets take a look...

Flowchart

The flowchart hopefully says it all. A single routine was defined; starting from the root directory, it uses a loop (see loop going back to F1.3 from F1.6) to circle through a folder, and in the process, launches a new instance of the same routine when a directory is encountered during the search (see F1.4 - F1.8). As seen from the chart, the newly spawned routine, at the end of everything, finally returns to the parent routine. So, no matter how many recursions we make, the program terminates at the end of the main program (if all goes well).

The code

Note: the entire sample code is written in pure C language, no proprietary API was used for portability reasons. And for those that mailed that the program created the "Recursion_out.txt" file but does not write anything in it, you might be having problems with your MSVCRT.DLL; get another one here, or look for programs that might replace it with working/upgraded versions.

Although the code is very short (essence of recursion), it was compiled using the Pelles C IDE for Microsoft Windows ver: 4.50 by Pelles Orinius (download here). But trying the code on another IDE (MSVCPP, GCC, and DEVC++ etc.) will probably give the same result. A friend compiled it on DEV C++ with 0 errors and 0 warnings, but I don't use it, so I can't say. :D And finally, I used "<" to prevent some HTTP errors (if I don't, the code will skip some steps).

Although the sample code is heavily commented, some people still prefer reading some straight explanation. Well, here you go: Starting from the defined sBuildList() function, the function receives three parameters:

1. Search path: The path to start the search from (e.g., C:\\ or "C:\\root folder\" for the C drive and "root folder", respectively). Just input a coated string of a path.
2. Output file handle: See the C _fopen() documentation.
3. Flag: To choose the desired output (screen/file).

int sBuildList(_TCHAR* path,FILE *file,unsigned int  flag){ 
    struct _finddata_t fs;//files search structure    
    long int  handle; //Search handle
    int counter=0;//?, see below

    //Here we created two (Hopefully) larg enough  buffers
    _TCHAR* buff = (_TCHAR*)malloc(MAX_PATH);
    _TCHAR* buff2 = (_TCHAR*)malloc(MAX_PATH);

    memset(buff,0,MAX_PATH);//Reset buffers to Zero
    memset(buff2,0,MAX_PATH);

    //Below, I Performed some string operations
    // to copy input string into the buffers FAST!
    for(int i=0;i"<"strlen(path);i++)
    //note i used coates around < to prevent some http errors
        buff2[i]=buff[i]=path[i];
    strcat(buff,_T("*.*"));

    //Searches starts
    if((handle = _findfirst(buff,&fs))==-1) //-1means error
        return 0;

    do{ 
        //Note: I GOT A PM SAYING memset is SLOW!, is that through?
        memset(buff,0,MAX_PATH);//Reset buffers to Zero
        memset(buff2,0,MAX_PATH);
    
        //I used the following line to copy text into the working buffers
        //I believe this method is faster in instead of using (l)strcpy,memcpy x2.
        for(int i=0;i"<"strlen(path);i++)
        //Copy data to the buffers
            buff2[i]=buff[i]=path[i];       
    
        /* I used "counter" to skip the two first directories (i.e . and ..).*/
        if(counter>=2){
            //below i rebuild "buff" to containe the new path or filename.
            strcat(buff,fs.name);
            strcat(buff,_T("\\"));
            //if it is a directory?,search it!
            if((fs.attrib & _A_SUBDIR)!=0)
            //Check for DIRECTORY
                //Take note as i recall the "sBuildList" here
                sBuildList(buff,file,flag);
                //DE SPOT! the recursion takes place here
    
            //if is a file...
            if((fs.attrib & _A_SUBDIR)==0){ //Check for FILE (ANY FILE!)
                strcat(buff,_T("\\"));
                strcat(buff2,fs.name); 
                strcat(buff2,_T("\n")); 
                if((flag & 1)==1){//standard output
                    printf(buff2);
                }else{
                    fputs(buff2,file);//output to file
                }
            }
        }
        counter++;
    }while((_findnext(handle,&fs))==0);

    _findclose(handle);
    free((void*) buff);
    free((void*) buff2);
    return 1;
};

The code is very self-explanatory, and short. It really justifies the nickname of "Divide and Conquer" of recursion (try the code and see for yourself!). Not much to explain here except that I used the simple string operation method above to copy the input path string into buffers simultaneously and directly, far better than using strcpy / memcpy (x2).The rest of the code uses the _findfirst and _findnext C-runtime functions in the do while loop to search for the files and directories (folders for MS Windows users). And finally, I closed the search handle and the allocated buffers. Done!

Conclusion

We have come to the end of the first part of this series. Subsequent parts will expose you to more advanced and mathematical topics on recursion, and applications to software programming. Do remember to rate this article as it will influence the release of more articles. And not to forget, greetings, reports, and corrections on this work are greatly welcome and will be appreciated. Look out for the next installments. Thanks.