Solved

recursion basics

Posted on 1998-01-03
9
290 Views
Last Modified: 2010-04-02
Could some explain recursion to me?  I mean, I get it, I understand that it's a function calling itself as many times as it needs to, but what is it used for?  Can you give me an example?  Can you explain when I would use recursion, vs. when I should just write an algorithm?

I'm looking for a fairly comprehensive answer, which is why I'm doling out 200 points...

Thanks,

Raydot.
0
Comment
Question by:Raydot
9 Comments
 
LVL 7

Accepted Solution

by:
galkin earned 200 total points
ID: 1256897
Example. You want to wrote a routine for deleting directory. To do this you need to delete all files in this directory and all subdirectories. To delete subdirectory you in turn must delete all files in this subdirectory and all subdirectories which given subdirectory may contain. Each two level subderictory may also contain files and subdirectories which must be deleted etc. So the only one way to implement such a function is to write a recursive function wich will call itself untill all files and subderetories are deleted then it can delete empty directory and return.

This is example of such a routine taken from my project

BOOL RemoveFilesFromDirectory(LPCTSTR lpszDir)
{
      WIN32_FIND_DATA fileData;
      HANDLE hFile;
      DWORD dwError;
      
      if(lpszDir[0] == TCHAR('\0'))
            return FALSE;

      TCHAR _szFile[_MAX_PATH];

      lstrcpy(_szFile, lpszDir);
      lstrcat(_szFile, _T("\\*.*"));

      hFile = ::FindFirstFile(_szFile, &fileData);
      if(hFile == INVALID_HANDLE_VALUE)
      {
            dwError = ::GetLastError();
            return (dwError == ERROR_NO_MORE_FILES);
      }

      while(::FindNextFile(hFile, &fileData))
      {
            TCHAR _szFile[_MAX_PATH];

            lstrcpy(_szFile, lpszDir);
            wsprintf(_szFile, _T("%s\\%s"), lpszDir, fileData.cFileName);

            if(lstrcmp(fileData.cFileName, _T(".")) == 0 ||
                  lstrcmp(fileData.cFileName, _T("..")) == 0
              )
              continue;

            if(fileData.dwFileAttributes & FILE_ATTRIBUTE_READONLY)
            {
                  ::SetFileAttributes(_szFile, FILE_ATTRIBUTE_NORMAL);
            }

            if(fileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
            {
// this is a directory we call this function againg recursiveely
                  RemoveFilesFromDirectory(_szFile);
            }
            else
            {
// this is file, we can simply delete it
                  if(!::DeleteFile(_szFile))
                        return FALSE;
            }

      }

      dwError = ::GetLastError();
// no more files in directory

      if(dwError != ERROR_NO_MORE_FILES)             
          return FALSE;

// empty directory is deleted
      if(!RemoveDirectory(lpszDir))
            return FALSE;

// we close search engine
      ::FindClose(hFile);

      return TRUE;
}

You must also use recursive function when you need to remove a registry key in uninstall routine or somewhere else. Since Windows NT doesn;t allow you to delete key which has subkeys and entries you must recursively delete them first.
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1256898
Basically, i guess, recursion is a chance each time a LIFO structure is appropriate.

BTW, you don't have recursion vs algorithm; actually, there are recursive and non-recursive algorithms.
0
 
LVL 3

Author Comment

by:Raydot
ID: 1256899
Galkin, the answer you gave me is pretty specific, and applies in what appears to be a highly specialized case (deleting file structures).  I need something a little more general and a little more basic, I think...

(Smacking forehead) Of course there are recursive algorithms...I knew that.  I just couldn't think of the word.  Non-recursive is much better, thanks, Julio.

What is LIFO?

0
Connect further...control easier

With the ATEN CE624, you can now enjoy a high-quality visual experience powered by HDBaseT technology and the convenience of a single Cat6 cable to transmit uncompressed video with zero latency and multi-streaming for dual-view applications where remote access is required.

 
LVL 1

Expert Comment

by:cph
ID: 1256900
Raydot,

LIFO: Last In First Out

Do you know factorial in math?
If so, it is a recursive process, you take the previous value and you multiply it with the new one and so on.

Hope this helps,

CpH.

PS: I can give a source code sample if you need to. However it is a simple exercise in which you can apply recursion. Send us the code if you have any problem
0
 
LVL 16

Expert Comment

by:imladris
ID: 1256901
Perhaps it should be noted here that any process that is "recursive" can be written without resorting to recursion. You may have to set up a stack to track relevant state information, but recursion perse (in the sense of a function calling itself) is not strictly necessary. It is, however, for a variety of problems, a cleaner and more elegant way of coding the solution.

Some other examples that come to mind beside dealing with directories and a math factorial calculation:

The towers of Hanoi problem
The implementation of a quicksort
The implementation of syntax processing in most compilers
      ( A statement is an assignment, a for loop followed by a
       statement or a block of statements, or a while loop followed
       by a statement or a block of statements)

0
 
LVL 3

Author Comment

by:Raydot
ID: 1256902
Yeah, I get the factorial bit...n * n-1 * (n-1)-1 * ... * 2 * 1, right?  That I can see.  imladris, you brought up some interesting examples, more of what I was looking for...maybe I'll just have to keep playing with it...

Thanks for your answer, Galkin...if anyone else has anything to add, I'm all ears: raydot@erols.com

Raydot.
0
 

Expert Comment

by:codeMaster
ID: 8108477
A recursive algorithm could be used in many different scenarios while programming, but in all of these cases (or at least most of them) iteration could be used as well.

Iteration is faster for run-time and doesn't take up so much space in memory. However, it is generally harder to code an algorithm iteratively than it is to code it recursively.

Recursion takes more space in memory because of the the overhead from the many function calls that are going on during the recursion. Every time the function calls itself the function name, and its local variables have to be copied into memory.

A recursive function always has a base case, and it always calls itself. These are its two main components. In a program dealing with multiplying numbers we might want to code it iteratively, however if we were going to find the factorial of some number we would want to code it recursively. For instance, if I was trying to find the factorial of a number the code (this is only a snippet) might look like this:

long double fact(long double);

int main()
{
    long double val;

printf("Enter a value for f: ");
scanf("%lf", &val);

printf("%lf! is %lf\n",val, fact(val));

return 0;
}


long double fact(long double num)
{
    if(num <= 1)
       return 1;
    else
       return (num * fact(num -1));  
       //This is where the recursion takes place
}

Hope this helps!




0
 
LVL 3

Author Comment

by:Raydot
ID: 8122743
I asked that question five years ago!  I actually teach C programming now, and was just explaining recursion to my students the other day.  Were you just digging around in the past, Codemaster?
0
 

Expert Comment

by:codeMaster
ID: 8132522
Wow, that is so funny.  I didn't look at the date : ) I actually found the question off of a google search. I was up late, and saw the question and decided to answer it. Oh my gosh, that is so funny. So, you are a C-programming teacher now. Wow, I am pretty shocked, that is really funny. Well, keep up the good work...I am a tutor at a college, tutoring students in C and Comp Sci and a few other computer courses. Its really great getting to perpetuate something that I love. All I can say is wow...
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question