Last Updated:

Recursion function in C++

Recursion is the last topic we'll cover in this chapter. Recursion, sometimes called cyclical determination, is the process of defining something on its own basis. In the field of programming, recursion refers to the process of a function calling itself. A function that calls itself is called a recursive function.


A classic example of recursion is the calculation of the factorial of a number using the factr() function. The factorial of the number N is the product of all integers from 1 to N. For example, the factorial of the number 3 is 1x2x3, or 6. A recursive way to calculate the factorial of a number is demonstrated in the following program. For comparison, its non-recursive (iterative) equivalent is also included here.

 

 

#include <iostream>

using namespace std;

int factr (int n);

int fact (int n);

int main ()

{

Use the recursive version.

cout << "The factorial of the number 4 is" << factr (4);

cout << '\n';

Use the iterative version.

cout << "The factorial of the number 4 is" << fact (4);

cout << '\n';

return 0;

}

Recursive version.

int factr (int n)

{

int answer;

if (n==1) return (1);

answer = factr (n-1)*n;

return (answer);

}

Iterative version.

int fact (int n)

{

int t, answer;

answer =1;

for (t=1; t<=n; t++) answer = answer* (t);

return (answer);

}


The non-recursive version of the fact() function is fairly simple and requires no extended explanation. It uses a loop in which successive numbers are multiplied, starting with 1 and ending with the number specified as a parameter: at each iteration of the cycle, the current value of the loop control variable is multiplied by the current value of the product obtained as a result of the previous iteration of the cycle.


The recursive factr function () is somewhat more complex.

 

If it is called with an argument equal to 1, it immediately returns the value 1. Otherwise, it returns the product factr (n-1) * n. To calculate this expression, call the factr () method with the argument n-1.

This process is repeated until the argument is set to 1, after which the previously called methods begin to return values. For example, when calculating the factorial of the number 2, the first call to the factr method () will result in a second call to the same method, but with an argument equal to 1.

The second call to the factr method () will return a value of 1, which will be multiplied by 2 (the original value of the n parameter). You might be interested in inserting cout statements into the factr() function to show the level of each call and the intermediate results.


When a function calls itself, the system stack allocates memory for new local variables and parameters, and the function code executes on those new variables from the outset. A recursive call does not create a new copy of the function.

 

Only the arguments are new. When each recursive call returns, the old local variables and parameters are retrieved from the stack, and the function resumes execution from the "inner" point of its call. Recursive functions can be said to be "pushed out" and "pushed".


Keep in mind that in most cases, using recursive functions does not significantly reduce the amount of code. In addition, recursive versions of many procedures execute more slowly than their iterative equivalents because of the additional system overhead associated with multiple function calls.

 

Too many recursive calls to a function can cause a stack overflow. Because local variables and parameters are stored on the system stack and each new call creates a new copy of these variables, there may be a point where the stack's memory is exhausted. In this case, other ("innocent") data may be destroyed. But if the recursion is constructed correctly, this is hardly worth worrying about.


The main advantage of recursion is that some types of algorithms are recursively implemented more easily than their iterative equivalents. For example, the Quicksort sorting algorithm is quite difficult to implement in an iterative way. In addition, some tasks (especially those related to artificial intelligence) are simply created for recursive solutions. Finally, some programmers have a thought process organized in such a way that it is easier for them to think recursively than iteratively.


When you write a recursive function, you must include a condition-checking statement (such as an if statement) that exits the function without making a recursive call. If this is not done, then, having once called such a function, it will no longer be possible to return from it. When working with recursion, this is the most common type of error. Therefore, when developing programs with recursive functions, you should not skimp on cout instructions to be aware of what is happening. in a specific function, and be able to interrupt its work in case of an error.


Consider another example of a recursive function. The reverse () function uses recursion to display its string argument in reverse order.

Display the row in reverse order by using recursion.

 

#include <iostream>

using namespace std;

void reverse (char *s);

int main ()

{

char str[] = "This is a test";

reverse (str);

return 0;

}

Output the string in reverse order.

void reverse (char *s)

{

if (*s) reverse (s+1);

else return;

cout << *s;

}


The reverse () function checks whether a pointer to zero that ends the string is passed to it as a parameter. If not, the reverse() function calls itself with a pointer to the next character in the string. This "twisting" process is repeated until the pointer to zero is passed to the same function. When the end-of-line symbol is finally found, there will be a process of "unwinding", i.e. the functions called earlier will begin to return values, and each return will be accompanied by an "additional execution" of the method, i.e. displaying the symbol s. As a result, the original string will be symbolically displayed in reverse order.


Creating recursive functions often causes difficulties for novice programmers. But with the advent of experience, the use of recursion becomes a common practice for many.