In C++, a recursive function is a function that calls itself directly or indirectly within the same function. It must contain at least one base class and a recursive condition. The base case helps to terminate the condition once it is completed. On the other hand, the recursive condition helps in the repetition of the code. In C++ , the recursive function will continue to loop until the base case is not satisfied.
Syntax
It has the following syntax:
void recursion(data_type parameter 1, ....)
{
//Code to be Executed
recursion(data_type param1, ....); //calling self
//Code to be Executed
}
In this syntax, we have taken a function name (data_type parameter 1….) that is declared as 'recursion' passing with several parameters. Here, the recursion function calls itself several times.
Simple Example of C++ Recursion
Let us take a simple example to find the factorial using the recursion in C++.
Example
#include <iostream>
using namespace std; //using standard namespace
int fact(int); //initialize fact as integer
int main() {
int num, res;
cout << "Enter the Positive Number: "; //input a number
cin >> num;
res = fact(num);
cout << "Factorial of " << num << " is: " << res; //print the result of fact
return 0;
}
int fact(int num) //recursion function calling itself
{
if (num > 1) {
return num * fact(num - 1);
} else {
return 1;
}
}
Output:
Enter the Positive Number: 6
Factorial of 6 is: 720
Explanation:
In this example, we have taken the fact function that is calling itself. Although, we have decreased the value of num by 1 during every call. When the num is less than 1, the fact function returns the output.
How Recursion Works in C++?
In C++, two cases are utilized in recursion that is Base Case and Recursion Condition.
1. Base Case:
In C++ recursion, a base class is a condition that helps to terminate the condition once it is matched. It defines the simplest scenario where the function does not call itself anymore. The base case defines when the recursion should stop. It prevents the infinite recursion and stack overflow. It ensures the function reaches a stopping point.
2. Recursive Condition:
In C++, the recursion condition is the condition where the function calls itself with a modified argument, which goes towards the base case. It helps in the repetition of the code.
Types of Recursive Function
There are mainly two types of recursive functions. These are as follows:
- Direct Recursion
- Indirect Recursion
Direct Recursion:
In C++, direct recursion happens when a function calls itself directly.
Syntax:
It has the following syntax:
void direct_recursion()
{
//code to be executed
direct_recursion() {
//code to be executed
}
C++ Fibonacci Series Example using Direct Recursion:
Let us take an example to illustrate the Fibonacci series using direct recursion in C++.
Example
#include <iostream>
using namespace std; //using standard namespace
int fibonacci(int num) // Direct Recursion Function
{
if (num == 0) return 0; // Base case
if (num == 1) return 1; // Base case
return fibonacci(num - 1) + fibonacci(num - 2); // Recursive case
}
int main() {
int number;
cout << "Enter the Number: ";
cin >> number;
cout << "Fibonacci Series: ";
for (int i = 0; i < number; i++) {
cout << fibonacci(i) << " ";
}
return 0;
}
Output:
Enter the Number: 5
Fibonacci Series: 0 1 1 2 3
Explanation:
In this example, we have taken an integer fibonacci (int num) function, which calls the direct recursion function. We also use (num==0) and (num==1) as a base case. After that, the user asks the user to enter the number and then, for loop, starts to print the Fibonacci numbers as the given condition. Finally, it prints the output in the console.
Indirect Recursion:
In C++, indirect recursion occurs when two or more functions call each other in a cycle.
Syntax:
It has the following syntax:
void indirect_recursion() {
//code to be executed
func();
//code to be executed
}
void func() {
//code to be executed
indirect_recursion();
//code to be executed
}
C++ Factorial Number Example using Indirect Recursion:
Let's take an example to find the factorial number using indirect recursion in C++
Example
#include <iostream>
using namespace std; //using standard namespace
int factA(int n); //function declaration
int factB(int n);
int factA(int n) //Here function A call the Function B
{
if (n == 1) return 1; // Base case
return n * factB(n - 1); //it calls the factB
}
int factB(int n) //Indirect function
{
if (n == 1) return 1; // Base case
return n * factA(n - 1); // Calls factA
}
int main() {
int num;
cout << "Enter the Number: ";
cin >> num;
cout << "Factorial of " << num << " = " << factA(num) << endl;
return 0;
}
Output:
Enter the Number: 6
Factorial of 6 = 720
Explanation:
In this example, we have taken two function in which function factA(int n) computes the factorial using the factB function, and factB(int n) computes the factorial using factA. After that, indirect recursion happens because the factA(n) calls the factB(n-1), and factB(n) calls the factA(n-1).
In the main function, the program asks the user to enter the number and calls factA(num) to calculate the factorial. Finally, it prints the output in the console.
C++ Program for Checking a Prime Number Using Recursion
Let us take an example to check a prime number using recursion in C++.
Example
#include <iostream>
using namespace std; //using standard namespace
bool primeNum(int num, int x = 2) //initialize boolean value
{
if (num <= 2)
return (num == 2) ? true : false;
if (num % x == 0)
return false;
if (x * x > num)
return true;
return primeNum(num, x + 1);
}
int main() //main function
{
int num;
cout << "Enter the Integer Number: "; //user input
cin >> num;
if (primeNum(num))
cout << "It is a Prime Number"; //print if number is prime
else
cout << "It is not a Prime Number"; //print if number is not prime
return 0;
}
Output:
Enter the Integer Number: 5
It is a Prime Number
Explanation:
In this example, the primeNum function is the recursive function that calls itself and checks whether the given number is prime or not based on the given condition.
Nested Recursion in C++
In C++, nested recursion is a type of indirect recursion where a recursive function creates another recursive call inside its own recursive call. It is mainly utilized to solve complicated mathematics and algorithm issues.
C++ Nested Recursion Example in C++:
Let's take an example to demonstrate the Nested Recursion in C++.
Example
#include <iostream>
using namespace std; //using standard namespace
int NestRecursion(int a)
{
if (a > 120) //using if condition
return a + 15;
else
return NestRecursion(NestRecursion(a - 20)); // Nested recursive call
}
int main() //main function
{
int num;
cout << "Enter the Number: "; //user input
cin >> num;
cout << "The Output is: " << NestRecursion(num) << endl; //print result
return 0;
}
Output:
Enter the Number: 130
The Output is: 145
Advantages and Disadvantages of Recursion in C++
Several advantages and disadvantages of recursion in C++ are as follows:
Advantages of Recursion in C++:
- It often leads to elegant and concise code, especially for problems with inherent recursive structures.
- It simplifies complex problems by breaking them down into smaller, more manageable subproblems.
- It can be versatile and applied to a wide range of problems.
- It helps to reduce the code length.
- It offers a clean and simple way to write the code.
- It consumes more memory due to the call stack, which leads to stack overflow errors for deep recursions.
- Recursive solutions may be less efficient than iterative ones, as each function call incurs overhead.
- Debugging recursive functions may be challenging because of the intricate call stack and multiple function instances.
- These functions are slower than other non-recursive function.
- It is difficult to understand.
Disadvantages of Recursion in C++:
Difference between Recursive and Iterative
Here's a comparison between recursion and iteration in tabular form:
| Aspect | Recursion | Iteration (Loop) |
|---|---|---|
| Control Flow | The self-referencing function calls itself. | Loop structure (for, while, etc.) controls flow. |
| Termination | It requires a base case to terminate the recursion. | It is controlled by a loop condition or counter. |
| Readability | It can sometimes lead to cleaner, elegant code. | It is typically more straightforward for simple tasks. |
| Memory Usage | It can consume more memory due to function calls. | It typically consumes less memory. |
| Code Complexity | It may involve less code for some problems. | It requires explicit loop control and iteration. |
| Handling State | It maintains a function call stack for the state. | It relies on variables for state management. |
| Tail Recursion Optimization | Some compilers optimize tail recursion. | There is no inherent optimization for loop tail calls. |
| Suitable Problems | Useful for problems with recursive structure. | Suitable for repetitive or iterative tasks. |
C++ Recursion MCQs
- Which of the following options shows the correct property of the recursion in the C++?
- Call to itself
- Base condition
- Return value
- All of the above
- How many base conditions are defined in C++ recursion function?
- More than two
- None of the above
- What will be the result of the given C++ program?
#include <iostream>
using namespace std;
int funct(int x)
{
if (x == 5)
return x;
else
return 2 * funct(x + 3);
}
int main() {
cout << funct(2);
return 0;
}
- Which of the following data structures is utilized to manage function calls in C++ Recursion?
- Heap
- Linked List
- Stack
- Queue
- What will be the output of the given C++ program?
#include <iostream>
using namespace std;
void Numb(int a) {
if (a > 0) {
Numb(a - 2);
cout << a << " ";
}
}
int main() {
Numb(7);
return 0;
}
- 1 2 3 4 5 6 7
- 1 3 4 5 6 7
- 2 4 6
- 1 3 5 7