Updated March 27, 2023
What is Recursion in C++?
Recursion in C ++ means creating a loop to perform a process in a repetitive manner to complete a particular task. Therefore, any function that calls itself again and again in code is called Recursive function. C ++ recursion is the most efficient and effective way of solving large and complex mathematical problems by dividing them into smaller tasks small line of code. The approach is also called as divide and conquer. The syntax for Recursive function in C ++ is given below:
Syntax:
void recursive_function() // Name of the recursive function
{
// Here is the function the will calls itself
recursive_function() ;
}
int main ()
{
recursive_function() ;
return 0 ;
}
In order to understand how a recursion actually works in C ++ let us see through a C ++ code that will help us understand step by step working of recursion in C++. But before that, we will discuss types of recursion in C ++ programming.
Types of Recursion in C++
There are two types of recursion:
- Direct Recursion
- Indirect Recursion
#1. Direct Recursion
When a function call itself directly, means it’s a direct recursive function. In below syntax, you can see we have defined a function with name recursive_function(). After that, we are calling the same recursive_function() inside recursive_fucntion(). This is the way of using direct recursion in your code.
Syntax:
void recursive_function()
{
recursive_function();
}
#2. Indirect Recursion
When a function calls itself indirectly, it means it’s calling the function with the help of another function defined is called indirect recursion. In below syntax, you can see we have defined a function with name function () and inside that, we have defined a recursive_function(). After that, we are calling the function () inside recursive_fucntion(). This is the way of using indirect recursion in your code.
Syntax:
void function ()
{
recursive_function () ;
}
void recursive_function ()
{
function () ;
}
Examples of Recursion in C++
Below are the examples of Recursion in C++.
Example #1
Here is the C + code to demonstrate the working of recursive function in C ++ programming language:
Code:
#include<iostream>
using namespace std;
int main ()
{
int factorial_num ( int ) ;
int facto, value ;
cout << " Please enter any number to find factorial of it : " ;
cin >> value ;
facto = factorial_num ( value ) ;
cout << " The Factorial of given number is: " << facto << endl ;
return 0 ;
}
int factorial_num ( int n )
{
if ( n<0 )
return ( -1 ) ;
if ( n == 0 )
return ( 1 ) ;
else
{
return ( n*factorial_num (n-1) ) ;
}
}
Output:
Here in the above code, you can see we have created a recursive function of the name factorial_num () of integer data type for calculating the factorial value of a given integer. We have also defined two integer variables with names facto, and value to calculate and store the value of a given integer number by the user. We have used if the condition for looping the value for calculating the factorial until the given number is not equal to zero. The moment value of n turn zeroes the loop will break and final value will be shown.
Example #2
Here is the C + + code to demonstrate the working of a recursive function and iterative function together in a single C + + programming language:
Code:
#include <iostream>
using namespace std ;
int factorial_fact ( int n )
{
if( n == 0 || n == 1 )
return 1 ;
return n * factorial_fact ( n-1 ) ;
}
int factorial_iterator ( int n )
{
int fact = 1 ;
for ( int i = n; i > 1; i--) {
fact *= i ;
}
return fact ;
}
int f[100] = {0} ;
int factorial_dynamic ( int n )
{
if (f[n] ) return f[n] ;
if ( n == 0 || n == 1 ) {
f[n] = 1 ;
return f[n] ;
}
f[n] = n*factorial_fact ( n-1 ) ;
return f[n] ;
}
int main()
{
cout << " The recursive factorial of number 15! = " << factorial_fact ( 15 ) << endl ;
cout << " The iterative factorial of the number 15! = " << factorial_iterator ( 15 ) << endl ;
}
Output:
Here in the above code, you can see we have created two recursive functions of the name factorial_fact() and factorial_interator() of the given integer data type in two different ways for calculating the factorial value of a given integer. We have also defined one integer variable with names fact where the default value of the fact is set to 1 initially. We have used if the condition for factorial_fact() function and for loop for factorial_interator() function for looping the value for calculating the factorial until the given number is not equal to zero. The moment value of n turn zeroes the loop will break and final value will be shown.
As a result, you can see both the functions are calculation the same value but in a different approach. But iteration function we used is slower than factorial function because for loop condition is there. Although in case of without iteration there is only one if the condition that will save a huge amount of time in traversing.
Conclusion
Recursion is helpful in writing simple and easy code. Some people use iteration instead of recursion but it is not that efficient. Recursive functions are small and require less memory and heap space therefore, they save a huge amount of time in the calculation and make your program faster.
Recommended Articles
This is a guide to Recursion in C++. Here we discuss different types of Recursion in C++ and its Examples along with its Code Implementation. You can also go through our other suggested articles to learn more –