🎇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
