Recursion is a very useful programming technique. It can be simply described as calling the function by the same function. It can be understood better by examples rather than by definitions.
A recursive algorithm must have the following,
- Base Case (to stop recursive call at some point)
- Recursive Call
Example:
Finding factorial of a positive integer.
The factorial of a positive integer is multiplication of a series of descending natural numbers.
eg:
eg:
4! = 4 x 3 x 2 x 1
In the above example note the following property.
4! = 4 x (3 x 2 x 1)
4! = 4 x 3!
Therefore for any positive integer n,
n! = n x (n-1)!
The above property enables us to use recursion.
If we write a function to find the factorial of a positive integer, let's call it 'factorial(int number)',
then
factorial(n) = n x factorial(n-1);
This is the recursive call.
The base case is the factorial of 1.
factorial(1) = 1;
Following is a program written in C to find factorial using a recursive algorithm.
[code]
#include <stdio.h>
int main()
{
int number;
printf("Enter an ineger: ");
scanf("%d",&number);
printf("The factorial is %d",factorial(number));
return 0;
}
int factorial(int number)
{
if(number == 1)
return 1;
return number*factorial(number-1);
}[/code]
#include <stdio.h>
int main()
{
int number;
printf("Enter an ineger: ");
scanf("%d",&number);
printf("The factorial is %d",factorial(number));
return 0;
}
int factorial(int number)
{
if(number == 1)
return 1;
return number*factorial(number-1);
}[/code]
No comments:
Post a Comment