Solved

# recursion basics

Posted on 1998-01-03
290 Views
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
Question by:Raydot

LVL 7

Accepted Solution

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;

{
::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

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

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

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

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

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...

Raydot.
0

Expert Comment

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

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

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

Question has a verified solution.

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

### 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…
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.