# Thread: could any one help me in understanding the concepts of recursive fns.

1. ## could any one help me in understanding the concepts of recursive fns.

i have a problem of understanding the recursive functions.I could not get the logic of implementing them correctly .
I want to learn them because it is one of the most important concepts of c.

2. >I want to learn them because it is one of the most important concepts of c.
I wouldn't say that, but recursion is a nice tool.

>I could not get the logic of implementing them correctly .
A function is a thingie (technical term) that holds stuff (highly technical term). Each thingie has it's own stuff, so you can make new thingies that look the same and it looks like you're using the same thingie inside of a thingie.

That didn't work? Okay, when you call a function, a new instance of all of the function's variables (along with return addresses and such) are placed in an activation record. This activation record could look something like this:

Local variables
Arguments

For the sake of pretty pictures, let's represent the above activation record like this:

func:
----------
|A|B|C|D|
----------

Now, when you call a function it places a new activation record with the necessary items on the stack (if there is no stack, it simulates that behavior, so we say it's on the stack to avoid drawn out explanations meant for accuracy...like this one). When you have two functions and one of them calls the other, a new activation record for that function is placed on top of the current record. This causes execution to enter the new function. When the new function returns, the activation record is popped from the stack and execution returns back to the calling function. The "stack" would look like this after the function call:

callee:
----------
|A|B|C|D|
----------
caller:
----------
|A|B|C|D|
----------

What if the callee is the same function as the caller?
Code:
```void caller ( void )
{
if ( something )
return;

caller();
}```
The exact same thing happens. A new activation record is created and pushed onto the stack:

caller:
----------
|A|B|C|D|
----------
caller:
----------
|A|B|C|D|
----------

It appears as if the same function is being run a second time, but in fact it is a completely different function that just happens to use the same template for the activation record as the calling function.

With the underlying concept understood (I hope), we can move on to the logic of implementing recursive functions. When designing a recursive function you usually just have to trust that it will work correctly, but the one thing that you must have is a base return condition. When the function has called itself enough times to solve the problem, you need a way to test for this and start the return path:
Code:
```#include <stdio.h>

void print ( int n )
{
if ( n == 0 )
return;

printf ( "%d ", n );
print ( n - 1 );
printf ( "%d ", n );
}

int main ( void )
{
print ( 5 );
printf ( "\n" );

return 0;
}```
If the function does not have a test (it could be anything) where one branch does not result in a recursive call, you have infinite recursion. New activation records will keep getting pushed onto the stack until you run out of some critical resource and the program crashes with a stack overflow error or something similar.

There are two rules for writing a recursive function: Each new recursive call should bring you closer to solving the problem and there must be a base case to end recursion.

Also remember that there are two paths for recursive execution, the path in and the path out. Both are shown in the code given above. The execution could be traced like this:
Code:
```n = 5, print and recurse
n = 4, print and recurse
n = 3, print and recurse
n = 2, print and recurse
n = 1, print and recurse
n = 0, return
n = 1, print and return
n = 2, print and return
n = 3, print and return
n = 4, print and return
n = 5, print and return```
The output you get is:
Code:
`5 4 3 2 1 1 2 3 4 5`
That's really all there is to it, you just have to wrap your mind around the concepts and you'll find yourself enjoying the power of recursion. It is a very useful feature of C when you get into complex algorithms and data structures.

3. Trivia question for the day: Who is the first to have said

To iterate is human, to recurse is divine.
Dave

4. Originally posted by Dave Evans
Trivia question for the day: Who is the first to have said
To iterate is human, to recurse is divine.
Dave
Hi Dave,

I came across the name L. Peter Deutsch, a couple of times with regards to the quote you posted.

~/

5. For most recursive functions you just have to 'trust' that it works. I would suggest that you start with some of the more basic recursive functions and work out some exercises on recursion. After that, if you have done data structures before, try doing some binary tree problems since they are recursive in nature. Thats how I got to understand a bit more about recursive functions

Also this may help a bit - as Prelude said you need a base case and each recursive call should work towards fulfulling that case. Also, for some of the more complex stuff, just take the simplest possible case and understand the logic to derive the recursive functions.

For example, if you had a big binary search tree, and you wanted to write a function that printed out all the information pre-order'edly, instead of trying to figure out how the whole thing is going to work, just look at a basic unit (say 1 parent and 2 children). If it works for that, then you can assume it will work with the rest of the tree for example. Then again I probably don't make much sense though

6. The linux kernel uses recursive functions to follow symbolic links, so they are very applicable. They are very useful to know about.