Recursion
A function is called recursive if a statement within the body of a function calls the same function.
Sometimes called as ‘circular definition’, recursion is a function calling itself in the definition.
A recursive function should have two parts recursive statement & a termination condition.
Suppose we want to calculate the factorial of an integer.
As we know, the factorial of a number is the product of all the integers between 1 and that number. Factorial of 4 can be expressed as 4! = 4 * 3! Where ! stands for factorial. Thus the factorial of a number can be expressed in the form of itself. Hence this can be programmed using recursion.
For Example
int fact (int); /*function definition*/
main( )
{
int n,ans;
printf(“Enter a number: ”);
scanf(“%d”,&n);
ans = fact(n); /*function call */
printf(“factorial = %d”,ans);
getch( );
}
int fact(int n)
{
if(n= =0) /*terminating condition*/
return (1);
return (n*fact(n-1)); /*recursive statement*/
}
Now let us evaluate this program:
Assuming the value of n is 3 when the control of the program is passed from the main( ) function the function fact. Since n is not equal to 0 so the condition is false and the recursive statement is executed.
3*fact(2)
now fact(2) is the calling function and thus the control of the program again reaches the beginning of the definition. Still the terminating condition is false so the recursive statement is executed.
2*fact(1)
again fact(1) is the calling function and thus the control of the program again reaches the beginning of the definition. Still the terminating condition is false so the recursive statement is executed.
1*fact(0)
now the condition is true so the answer to the calling function(fact(0)) will be 1 and so on. Thus the sequence of acts will be:
fact(3)=3 * fact(2)
fact(2)=2 * fact(1)
fact(1)=1 * fact(0)
When we use a recursive program a stack is used to organize the data. Stack is a Last In First Out (LIFO) data structure. This means that the last item to be stored (push operation) in the stack will be the first one to come (pop operation) out. In the above program when the fact(2) is called the value 3 will be stored in the stack. Similarly when fact(1) is called the value 2 will be stored at the top of 3 on the stack.
Now when the fact(0) returns 1. It will be multiplied to the first value in the stack i.e. 1. This result will be multiplied to the second waiting value of the stack i.e. 2 and so on.
When a function in its definition calls another function it is called chaining.
Recursion is a special type of chaining where a function calls itself.
For Example
main( )
{
printf(“Matrix \n”);
main( );
}
when executed the program will give the output as:
Matrix
Matrix
Matrix
_
_
The execution of any recursive function can continue indefinitely so to bring the execution to the end a terminating condition is applied.
Use of recursive is to solve the problem where the solution is expressed in terms of successively applying the same solution to subsets of problems. But there are also some disadvantages of the recursive functions:
1.These functions are more time consuming, so the execution speed of the program is slow.
2.More memory space is occupied due to the formation of stack to keep the waiting values.
