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:
Output:
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:
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
|
|||||
void TrialRecursion(int count)
{
if(count==0)
return;
else{
printf("Welcome msg no:%d\n",count);
TrialRecursion(count-1);
return;
}
|
4
|
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
|
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
|
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
|
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
|
Action: pop all till control returns to main function
|
|||||
void main()
{
int count=5;
TrialRecursion(count);
}
|
|
|
|||||
|
|
|
Advantages:
- Can simplify a complex task by breaking into smaller repeatable tasks.
- Provides Alternative to complex looping.
- Simple code.
Disadvantages:
- More Memory is utilised to store the function state onto the stack.
- May lead to stack overflow in case of large functions with lots of variables.
- Debugging the program is difficult.
- Decreases the time efficiency of program.
No comments:
Post a Comment