Recursion is an effective approach to dissolve the issues like complex mathematical computations tasks. This is done by distributing the task into sub-tasks. This process is done by following the divide and conquer rule. It’s not a mandatory thing to always use a recursion process in your program for the repetition. Any problem that is resolved through recursion can also get solved through iteration. But the recursive function is more efficient in programming as the code is very short and easily understandable while performing the same task. The recursion process is always recommended for issues like searching and sorting, tree traversals, etc.
Note: The recursion process must have a terminating condition or a base class. In the second case, it will lead to infinite executions like a loop of iterations.
Syntax of recursive function (C++)
The basic syntax of recursive function is given as:
// Statement(s)
recurse(); }
The concept is to divide a problem into many smaller problems and then add all the base conditions that can stop the recursion.
Base condition
In any recursive program, the solution of a bigger problem is expressed in smaller problems.
{
if (n < = 1) // base case
return 1;
else
‘other statement’
}
The statement/condition of ‘n < =1’ is defined here, and hence the larger value can be solved by converting to a smaller one until the condition of the base case is fulfilled. If we don’t use a base condition in our program, then there will be no ending point specifying the code, the infinite execution will occur. Here we will use a sample example.
Simple function
Now consider a sample of a recursive function in which we take a value in the main program and then pass it to the function. Inside a function, we use an if-else statement. The ‘if’ part of the statement refers to the base condition to terminate the function or to limit the output. This will be applied when the value is less than 1.
Whereas the main feature is applied on the ‘else’ part of the function. This is the recursive function.
The value is displayed before and after this statement, so the output will contain the numbers in descending and in ascending order. The execution of the code is done through a g++ compiler. ‘-o’ is used to save the output of a source code in an output file.
$ ./r1
Now, we want to see the effect of the base condition in this program. We will see the resultant value; if we remove the if-else statement from the same program as described above, what will be the output.
You can see that the rest of the code is unchanged after removing the conditional statement. After removing the base statement, the output will look like the below image. There will be no defined endpoint for this execution. You can notice that the output is an infinite sort of a single number.
This same output lasts many lines until a message of core dump is shown.
Working of recursion
Suppose a programmer is willing to determine the sum of the first n numbers, there are many ways to determine the sum, but the simplest one is to add the numbers by starting from 1 to n. So the function will look like this:
The above example is the simple addition of the numbers. The second approach deals with the usage of a recursive function.
F(n)= n + f(n-1) n>1
Now you can point out the difference between both the approaches. In the second approach, f() is a basic dissimilarity, as it is itself called.
Recursion is of two types. One is direct recursion. The second is an indirect recursion. A function is called an indirect recursive if it has a function call for another function and that other function calls the first function directly or indirectly. A sample for direct recursion is illustrated as:
F (n);
//some code}
Whereas a sample for the indirect recursion is represented as:
f1(); }
void f1( int n) {
f();
return; }
We will now elaborate on both types of recursive functions through some basic examples.
Direct recursion
Example 1
This example deals with the calculation of the Fibonacci series. Again the concept is the same; a conditional statement is used here to stop the condition; the value should be equal to zero. Otherwise, if the value is equal to 1 or 2, it will return 1. As this series formation needs 2 numbers, so the number used in the main program should be greater than 2. The statement formula for the Fibonacci is written in the ‘else’ art of the condition. This is mainly the recursion of the program.
Whereas the main function will initiate the functional call bypassing the value. This value is a number up to which the output should be. The output can be checked through the Linux terminal by a g++ compiler.
Example 2
This example deals with the factorial calculation of a number. For this calculation, a number must be greater than 1, so here we have applied a base condition; if this part of the ‘if’ statement is fulfilled, then the program will be terminated; otherwise, the mathematical operation is applied to the number.
This is the recursion function, in which the answer of the function is again utilized in the function call.
The resultant value is shown below.
Indirect recursion
We will apply the same calculation of factorial indirectly. As we have described earlier, that in indirect recursion, the functions don’t call it, so we need another function for this purpose. Take an example that has two functions. In function A, the recursion function is declared in the same way as in the previous example, but the function call is for the second function, Function-B. Function B contains the same calculation method, and it contains the recursive call for function A.
In the main program, a function call to function A is made.
When you see the output, you will notice that the answer for both the recursion methods is the same, but only the difference is in the approach used.
Conclusion
‘C++ recursive function’ has many advantages as it is used in the searching and sorting processes. The base condition has the main role in the execution of recursion, as it limits the output and infinite execution. The commonly used examples are explained here to provide the user understanding of recursion.
