>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
Return address
Link to the previous record
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.