Solved

recursion basics

Posted on 1998-01-03
9
288 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
 
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

743 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now