Recursion

Recursion is a programming technique used in place of iteration. Methods, procedures or function used recursion calls itself until given condition is satisfied. Often required multiple loops and it make the program too complex. The loops can be replace into small functions with recursive technique and it simplified the program and easy to understand. However, recursive function had some disadvantage too. The recursive needs more space and time as the variables used in function call

¨       Linear Recursion

¨       Tail Recursion

¨       Binary Recursion

¨       Mutual Recursion

¨       Nested Recursion

1.    Linear Recursion is a function that calls itself in a simple manner. The function terminates and return to the caller function when given condition satisfied. The process is known as ‘Winding’ and 'Un-Winding'. The condition given for termination once reach the required limits and to return to the caller. The termination condition also called as Base condition.

Example:

     int fact(int n)
         {
              if(n<=1)
                 return 1;
              else
                    return ( n* fact(n-1));
         }
 

2.    Tail Recursion - When recursive call occurs at the end of a method it is called a tail recursion. The function perform all the statements before hopping to the next call.

Example:

     int gcd(int x, int y)

        {

             if(y<=0)

                  return x ;

             else

                  return(y,x%y) ;

        }

   

3.    In binary recursion, a function calls itself twice.

  Example:
         void fibo(int n)
          { 
               if( n <= 2 )
                            return 1;
               else
                          return fib(n-1)+fib(n-2);  
         }

4.    Mutual Recursion when the functions called each other. In following example the fun

Example:

     boolean Even(int n)

        {

             if(n%2==0)

                  {

                       return true;

                  }

             else

                       return Odd(n);

        }

     boolean Odd(int n)

        {

             if(n%2!=0)

                  {

                       return false;

                  }

             else

                       return Even(n);

        }

5.    Nested Recursion is an exception as all other recursive function can be written using loops except this one.  In nested recursive, each recursive function calls another recursive function and this cannot be replace by simple iteration.

Example:
 

    int Num(int n)

     {

         if(n>= 10)

             return  n - 1;

         else

             return Num(Num(n + 3));

     }