Recursion
A function call is said to be recursive, if we invoke a function from within the same function. The phenomenon being referred to as recursion. A termination condition must be specified with each recursive call to avoid infinite execution of that function. Recursion is basically required whenever a function has to operate upon different set of values to obtain the result.
The recursive calls must store the intermediate results of arguments of arguments and local variables. Recursive calls cannot store these values in the memory allocated to variables during compile time, hence dynamic memory management issues are involved in recursion. Thus, the arguments must be stored along with the return address to evaluate the result, since most recently saved variables are restored first. Thus activation stacks are created which support LIFO (Last In First Out) order for the purpose of evaluating result in recursion.
Thus recursion may also be used in programs that must operate in Last In First Out order. Recursive programs may also be written using non-recursive approach to programming either with the use of stack or by using GOTO to transfer the control to any specific part of the program, wherever required. However, some recursive functions may be converted to iterative definitions simply by using an iterative construct.
Recursion is explained further with examples such as computing factorial of a given number, computing GCD (Greatest Common Divisor), solving Towers of Hanoi problem, raising a number to a given power etc.
Recursive function to find the factorial of a given number:
/*Recursive Definition*/
int factorial(int n)
{if(n==0)
return 1;
else
return(n*factorial(n-1));
}
As the above definition implies, computing a factorial using recursion is similar to computing method performed manually. The recursive function may be converted to non-recursive/iterative function as follows:
/*Non-Recursive Definition*/
int factorial(int n)
{int i,res=1;
for(i=n;i>=1;i–)
res=res*i;
return(res);
}
If we compare the recursive definition with the iterative one, we note that recursion is eliminated by using a for loop for operating n times restoring the value at each call in a variable called res. Thus, we may write a recursive algorithm considering the basic step required to sort out a given problem.
Recursive function to solve Towers of Hanoi Problem:
This problem is all about shifting disks from one pillar to the other pillar using a third pillar such that only one disk from the top may be moved at a time such that it is transferred to one pillar while considering that larger disk should be at the bottom of smaller disk. Recursion is used to solved Towers of Hanoi problem, since it involves repetitive shifting of disks from one pillar to the other. The ‘C’ recursive function for the same is given below with the output to trace the execution of the program:
void hanoi(int num_disks,char *src,char *tmp,char *trgt)
{
if(num_disks==1)
{printf(“nMove disk from %s to %s”,src,trgt);
}
else
{
hanoi(num_disks-1,src,trgt,tmp);
printf(“nMove disk from %s to %s”,src,trgt);
hanoi(num_disks-1,tmp,src,trgt);
}
}
Recursive function to compute GCD of a given number:
To compute the greatest common divisor of two given numbers x and y, if x is lesser than y, then GCD is invoked with alternate set of arguments. If the second argument y=0, the first argument x is returned, otherwise GCD function is called with the arguments as y and xmody. The ‘C’ function for computing GCD is given below:
/*Recursive function to compute GCD*/
int GCD(int x,int y)
{
if(y==0)
return x;
else if(x<y)
return GCD(y,x);
else
return GCD(y,x%y);
}
Recursive function to compute power of a given number:
The power of a given number may be computed by using the following function, f(x,n):
f(x,n) = 1 ; if n=0
x * xn-1 ; if n>0
/*Recursive definition to computer power of a given number*/
int power(int x,int n)
{
if(n==0)
return 1;
else
return(x * power(x,n-1));
}