anoopelias/Recursion.md

## Recursion.md

      
    Raw
  

              Recursion.md
            
          
    There are two forms of recursion,


Tail Recursion : The return value is calculated as a combination of the value of current subroutine and the return value of the next call. Example,
 int factorial(int a) {
     if(a==0)
         return 1;
     else
         return a * factorial( a-1 );
 }


Accumulator based recursion : You accumulate the results by adding an additional parameter and return the accumulated value.
 int factorial(int a, int fact) {
     if(a==0)
         return fact;
     else
         return factorial(a-1, a*fact);
 }


Tail recursion is considered more readable, while it can cause a StackOverflow!. This is because it has to push the current value to a stack, before calling subroutine again. And when you make a large number of such calls, this stack might go over its limit.
Some compilers optimize tail recursion to accumulator based in order to avoid this problem.