Recursion is a powerful programming technique in which either a single Function calls itself again and again (direct recursion) or two functions call each other again and again (indirect recursion) till the final calculation of the result. Involved function(s) in the recursion, is called recursive function. The number of times a function is called recursively is called depth of recursion.
Recursion is a fundamental concept in computer science. The feature of calling a function from itself was not supported in older programming languages like FORTRAN, COBQL, and BASIC. But all latest modern programming languages support recursion.
Conditions for Recursive Function
There are two important conditions that must be satisfied by any recursive function. These conditions are necessary to prevent the recursive function from running infinitely. The conditions are:- A recursive function must have a non-recursive part, called the base criteria. It is a criteria or condition used to terminate the execution of the recursive function.
- Each time the recursive function is called directly or indirectly, the condition must get closer to the base criteria.
A recursive function that fulfills these two conditions is celled a well defined recursive function.
Implementation of Recursive Function by Stacks
A recursive function can be executed several times depending on the situation. It receives values from the calling function and transmits results back to it. For its proper functioning, it must save the parameters and variables upon execution and restore these parameters and variables at completion. While returning values, the function must keep track of the return address in the calling function. This return address is used to transfer the control back to its proper place in the calling function. It saves the return address of each calling function in the same order in which it is called and returns the control to proper place in the calling function each time the control is returned.The recursive function terminates execution when the base criteria is reached. Then it returns parameters and variables to the calling function. It returns these values such that the values from the last execution are returned first. This last-in and first-out characteristics of a recursive function shows that a stack is the most suitable data structure to implement it. At each function call, the stack is pushed to save the necessary values upon exit from the function, the stack is popped to retn'eve the values
The general algorithm for a recursive function contains the following three parts:
| Parts | Brief Description |
|---|---|
| Prologue | It is the opening part of the recursive function. Its purpose is to save the formal parameters, local variables and return address. |
| Body | It contains the definition of the function, including the test criteria, in which the function calls itself. Each time the function calls itself, the prologue of the function saves all necessary information required for its functioning. |
| Epilogue | It is the last part of the recursive function. It restores the most recently saved parameters, local variables and return addresses. |
IF n = 0 THEN n! = 1From steps 1 to 3, the factorial is evaluated in terms of factorial of another integer.
IF n = 0 THEN n! = n * (n-1)!
step 1 3! = 3*2!
step 2 2! = 2*1!
step 3 1! = 1*0!
step 4 0! = 1
step 5 1! = 1*1 = 1
step 6 2! = 2*1 = 2
step 7 3! = 3*2 = 6
Step-4 explicitly evaluates factorial of 0 as 1. Therefore "0!" is base value of the recursive definition.
After reaching the base criteria, the evaluation is performed in the reverse order.
The factorial of 0 is used to find out the factorial of 1. Similarly, 1! is used to find out 2! and so on.
C++ Example Program of Recursive Function
The following source code of the program find out the factorial of a given number by recursive function.Suppose the factorial of 5 is to be calculated. The recursive process to find its factorial is shown in the following image.
#include
#include
main()
{
long fact (int), n;
clrscr();
cout
cin>>n;
cout
}
// member function to find factorial
long fact (int x)
{
if (x == 1)
return 1;
else
return x * fact (x-1);
}
What is Recursive Programming
The concept of recursive programming is different than that of other programming approaches. A simple mathematical operation is given below to explain the concept of recursive programming.For example, the sum ef values between 1 and 10 is equel to10 plus the sum of values between 1 and 9. Continuing this idea, the sum of values between 1 and 9 is equal to 9 plus the sum ef values between 1 and 8 and so on.
In C++, a function can call itself. Each call the function creates a new environment to work. For example, to compute the sum of numbers between 1 and N, the reeureive mathematical technique is given below:
(this part comming soon)
When a function calls itself, all local variables and parameters are newly defined. and a unique space is allocated on the stack. The function is executed with new parameter. values from the beginning. A recursive call does not make a new copy of the function but only the arguments are now. As each recursive call returns, the local variables and parameters of previous function call are removed from the stack and new variables and parameter values are added into it.
A recursive function to compute the sum of values between 1 and N is defined below:
int sum (int N)In the above recursive function definition, the sum of the numbers between 1 and N is equal to N plus the sum of numbers between 1 and N - 1. The parameter passed to the function “sum” is decremented each time the function is called, so that it will get closer to the base case (such as 1). Each time intermediate value is pushed into stack. When parameter value is equal to 1 then calling process of recursive function is stopped. The recursion begins to fold back into the earlier versions of the function “sum” by popping their values to calculate the results and returning the calculated value each time. Each returned value contributes to the computation of the sum at the higher level.
{
if (N == 1)
return 1;
else
return = N + sum (N - 1);
}
A diagram is given below to show recursive process when main() function calls "sum" to compute the sum of the values between 1 and 4. Each box represents the function call with new variables and parameter (N-1). When the base case is reached then the calls begin to return their results.
The steps to compute the sum of integers between 1 and 4 using recursive definition are given below:
IF N = 1 Then return 1From Step-1 to 3, the values in stack will be added in the following order:
ELSE
step-1= sum between 1 and 4 = 4+sum between 1 and 3
step-2= sum between 1 and 3 = 3+sum between 1 and 2
step-3= sum between 1 and 2 = 2+sum between 1 and 1
step-4= sum between 1 and 1 = return 1
step-5= return 2+1 = 3
step-6= return 3+3 = 6
step-7= return 4+6 = 10
- 4 will be added in step 1.
- 3 will be added in step 2.
- 2 will be added in step 3.
At step-4. the base ease ie reached. Therefore, the evaluation is performed in the reverse order. The value 1 is returned at this step. Thie value is ended to 2 which is stored at the top of stack returned at previous step and 2 is removed from stack. Then 3 will be removed from stack and it is added to the result value and so on.
Read: Important File Operation Modes in C++
Example program 2: The following source code of the program find the exponential power of an integer value by c++ recursive function.
#include
#include
class exponent:
{
public:
// member function to find exponential power
int power (int b, int n)
{
if (n == 0)
return 1;
else
return b * power (b, n-1);
}
};
void main (void)
{
exponent obj;
int val, p, res;
clrscr();
cout
cin>>val;
cout
cin>>p;
res = obj .power (val, p);
cout
getch();
}
