Recursion

It is a function that once called in main function will call itself until the exit condition is satisfied.
Program to find factorial of a number using recursion. 
           #include<stdio.h> 
           void main() 
           { 
                    int n,res; 
                    printf("enter the no "); 
                    scanf("%d",&n); 
                    res=fact(n); 
                    printf("Factorial is:%d",res); 
           } 
           int fact(int n) 
           { 
                    if((n== 1)||(n==0)) 
                           return 1; 
                    else 
                           return(n*fact(n-1)); 
           } 

Working:
              If n=5 
                       5*fact(4) 
                       4*fact(3) 
                       3*fact(2) 
                       2*fact(1) 
                       1*fact(0) 
output=120 

Advantages: 
  • Reduces the code size. 
  • Represents compact programming. 
Disadvantages: 
  • Exit condition is a must for recursive statements else leads to stack overflow. 
  • Slower than looping statements. 

Function calls also have memory requirements. They need to store values for parameters, local variables, and an address for a return value. This memory comes from the stack during the function execution. After the function has completed, the memory is released back to the stack. 

During recursion, function calls continue to require more and more stack memory which does not get released until the recursive chain terminates. Stack overflow results when memory allocations are beyond what the stack is able to provide. So if a function has too many levels of recursive calls, one can run out of memory.
In general, a recursive function will consume more stack space (since it's really a large set of function calls), while an iterative solution won't. This also means that an iterative solution, in general, will be fast. 
Conclusion:
Recognize that recursion has its costs and cannot be used without boundaries.

No comments:

Post a Comment