Recursive Function

Recursive Function

A function which calls itself directly or indirectly again and again is known as the recursive function. Recursive functions are very useful which constructing the data structures like linked lists, double linked lists and trees. There is a distinct difference between normal and recursive functions. A normal function will be invoked by the main function whenever the function name is used, whereas the recursive function will be invoked by itself directly or indirectly as long as the given condition is satisfied.

   For example,

          #include <iostream.h>

          void main(void)

          {

                void funct1( );//function declaration   

                    

                funct1( );//function calling

          }

          void funct1( )//function declaration

         {

                  

               funct1( );//function calls recursively

        }

PROGRAM

A program to find the sum of given non-negative integer numbers using a recursive function.

     Sum = 1+2+3+4…n

    //sum = 1+2+3+4…n using recursive function

   #include <iostream.h>

   void main(void)

   {

       int sum (int);

       int n, temp;

       cout << “Enter any integer number” << endl;

       cin >>n;

       temp = sum (n);

       cout << “value = “ n << “and its sum = “ << temp;

   }

   int sum (int n) / / recursive function

   {

       int sum (int); / / local function declaration

       int value = 0;

       if (n == 0)

           return (value);

           else

                 value = n+sum(n-1);

                 return (value);

    }

Output of the above program

    Enter any integer number

    value = 11 and its sum = 66

    The following illustrations will be helpful to understand the recursive function

          For value 1                                   For value 2

        = 1+sum(1-1)                              = 2+sum(2-1)

        = 1+0                                         = 2+1+sum(1-1)

        = 1                                             = 3

       For value 3

       = 3+sum(3-1)

       = 3+2+sum(2-1)

       = 3+2+1+sum(1-1)

       = 6

PROGRAM

A program to find the factorial of the given number using the recursive function.

    The factorial of n (written n!) is the product of all integers from 1 to n.(assume n is non-negative).

 

         1            n = 0

n! =

         n(-1)!     n>0

/ /factorial of a given number using recursive function

#include <iostream.h>

void main (void)

{

      long int fact (long int);

      int x,n;

      cout << “Enter any integer number” << endl;

      cin >> n;

      x = fact (n);

      cout << “value = “ << n << “ and its factriocal  = “

      cout << x << endl;

}

long int fact (long int n) / / recursive function

 {

      long int fact (long int); / / local function declaration

      int value = 1;

      if (n == 1)

         return (value);

      else

            {

                 value = n * fact (n-1);

                 return (value);

            }

 }

Output of the above program

     Enter any integer number

    Value = 5 and its factorial = 120

Illustrations

   For value 1                            For value = 2

      = 1*fact(1-1)                           = 2*fact(2-1)

      = 1                                         = 2*1

                                                    = 2

   For value 3

      = 3*fact(3-1)

      = 3*2*1

      = 6