The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called recursive function.
1.Direct recursion : If a function calls the same function then it is known as direct recursion.
Example :
void func( )
{
//some code.....
func( );
//some code....
}
2.Indirect recursion : If a function calls a different function it is known as indirect recursion.
Example :
void func1( )
{
//some code.....
func2( );
//some code....
}
void func2( )
{
//some code.....
func1( );
//some code....
}
The recursion continues until a particular condition is met to prevent it from entering it into an infinite loop.
Below is an example of finding the factorial of a given number using recursion.
A factorial is the product of an integer and all the positive integers less than it. A factorial is denoted by the symbol !
For example,
4! (read as four factorial) represents the following:
#include<stdio.h>
int factorial(int n)
{
if(n==0||n==1) //Stop condition
return 1;
else
return n*func(n-1) ;
}
int main( )
{
int n;
printf("Enter the number to find it's factorial ") ;
scanf("%d",&n);
printf("Factorial of %d is : %d",n,factorial(n);
return 0;
}
Output :
Enter the number to find it's factorial 4
Factorial of 4 is : 24
Memory Allocation in recursion
When a function is called the memory is allocated for it on a stack, the memory for a called function is allocated on top of the memory allocated to calling function and a different copy of local variables is created for each function call.
When the base(stop) condition is reached the function returns it's value to the function by whom it is called and memory is de-allocated and the process continues.
Below is an illustration of Memory Stack
As we can see above the factorial(1) returns 1 to factorial (2) and factorial(2) returns 2*1 to factorial(3) and factorial (3) returns 6(3*2*1) to factorial(4) Returns 24(4*3*2*1).
0 Comments