Recursion in data structure

                                🎇Recursion🎇

Definition: Recursion is a programming technique in which                                the function call itself repeatedly for some input.

Factorial function:
one can define the factorial of some number n as a product of all the integers from n to 1.

FOR EXAMPLE:

if the 5 factorial has to be calculated then,it will be=5*4*3*2*1=120

similarly 3!=3*2*1=6 and the 0!=1.
The exclamation mark is used to denote factorial.we may write the definition of factorial function as-

   n!=1 if n==0
   otherwise,n!=n*(n-1)*(n-2)*.........*1 if n>0
If the value of n is any of the 0,1,2,3 then the definition will be-
0!=1
1!=1
2!=2*1
3!=3*2*1

Here we are presenting an algorithm that takes the input as value of n and  returns the results of n!.There are two ways of doing this-

1.Iterative method     2.Recursive method

🎇Algorithm for factorial function using                  iterative definition:

prod=1;
x=n;
while(x>0)
{
prod=prod*x;
x--;
}
return(prod);

such as algorithm is called as an iterative algorithm because it calls explicit repetition of some process until certain condition is met(for example x>0)

The definition of factorial is

   n!=1 if n==0

otherwise,n!=n*(n-1)*(n-2)*....*1 if n>0

This definition is called the recursive definition of the factorial function.This definition is called recursive because again and again the same procedure of multiplication is followed but with the different input and result is again multiplied with the next input.Let us see how the recursive definition of the factorial function is used

to evaluate the 5!

step 1:5!=5*4!
step 2:          4!=4*3!
step 3:                    3!=3*2!
step 4:                              2!=2*1!
step 5:                                        1*0!
step 6:                                             0!=1.

Actually the step 6 is the only step which is giving the direct result.so to solve 5! we have to backtrack from step 6 to step 1,collecting the result from each step.Let us see how to do this.

step 6`: 0!=1
step 5`:         1!=1*0!=1
step 4`:                    2!=2*1!=2
step 3`:                              3!=3*2!=6
step 2`:                                    4!=4*3! =24      
step 1`:                                          5!=5*4!=120


Algorithm for factorial function using the Recursive definition:

if(n==0)
fact=1;
else
{
x=n-1;
y=value of x!;
fact=n*y;
}

Advantages:

1) Recursive methods bring compactness in program.

2)There is no need of using programming construct such as                 for,while,do-while.

Disadvantages:

1)Memory utilization is more in recursive functions because all           pending operations must be preserved.

2)Recursive methods are less efficient than iterative methods.

3)Recursive methods are complex to implement.

Properties of Recursive definition:

The very essential property of recursive definition is that there should be atleast one non recursive call,because of which the procedure won`t go in the infinite condition.Thus the non recursive

exit will help a recursive procedure to terminate.

FOR EXAMPLE:

if(n==0)

  return 1;

is a non recursive 

call for factorial

Another property of recursive function is that any instant of recursive definition must eventually reduce to some manipulation.By this one can reach to the answer after certain number of steps.

🎇program for finding out the factorial for any given number.

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

void main(void)

{

int n,f;

int fact(int n);

clrscr();

printf("\n program for finding factorial number");

printf("\n enter the number for finding the factorial");

scanf("%d",&n);

f=fact(n);

        printf("\n The factorial of %d is %d",n,f);

getch();

}

int fact(int n)

{

int x,y;

if(n<0)

{

printf("the negative parameter in the factorial function");

exit(0);

}

if(n==0)

{

return 1;

x=n-1;

y=fact(x);

return (n*y);

}

}

output:

program for finding the factorial number

enter the number for finding the factorial=5

The factorial of 5 is 120