FoodForFutureGeeks

Monday 16 April 2012

Recursion

Recursion is a concept in which a function calls itself till a certain condition is satisfied, the function call states are stored on a stack.(ie the local variables,registry values etc)
Once the required condition is satisfied, the control is returned back in order the functions were pushed into stack.

sample program:


#include<stdio.h>
void TrialRecursion(int count);
void main()
{
 int count=5;
 TrialRecursion(count);
}
//this function prints the welcome message 5times or equivalent to count
void TrialRecursion(int count)
{
 //required condition for final return
 if(count==0)
    return;
//else print welcome message and call itself with count-1 as parameter
 else
  {
   printf("Welcome msg no:%d\n",count);
//Recursive Call
   TrialRecursion(count-1);
   return;
   }
}

Output:

1
2
3
4
5
Welcome msg no:5
Welcome msg no:4
Welcome msg no:3
Welcome msg no:2
Welcome msg no:1


Control Flow and stack during Recursion:



Function  Control   Flow
count
Stack
void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

5
Action:  push function state
TrialRecursion()count=5
void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

4
TrialRecursion()count=4
TrialRecursion()count=5
Action:   push function state
void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

3

TrialRecursion()count=3
TrialRecursion()count=4
TrialRecursion()count=5
Action:  push function state
void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

2

TrialRecursion()count=2
TrialRecursion()count=3
TrialRecursion()count=4
TrialRecursion()count=5
Action:  push function state
void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

1
TrialRecursion()count=1
TrialRecursion()count=2
TrialRecursion()count=3
TrialRecursion()count=4
TrialRecursion()count=5

Action:  push function state






void TrialRecursion(int count)
{
if(count==0)
   return;
else{
 printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}

0
TrialRecursion()count=1
TrialRecursion()count=2
TrialRecursion()count=3
TrialRecursion()count=4
TrialRecursion()count=5

Action:  pop all till control returns to main function

void main()
{
 int count=5;
 TrialRecursion(count);
}


 Control returns to main function.







Advantages:

  1. Can simplify a complex task by breaking into smaller repeatable tasks.
  2. Provides Alternative to complex looping.
  3. Simple code.

Disadvantages:

  1. More Memory is utilised to store the function state onto the stack.
  2. May lead to stack overflow in case of large functions with lots of variables.
  3. Debugging the program is difficult.
  4. Decreases the time efficiency of program.




No comments:

Post a Comment