In C++, a recursive function refers to a function that invokes itself either directly or indirectly within its own body. It is a requirement for the function to have a minimum of one base case and a recursive condition. The purpose of the base case is to stop the recursion once a certain condition is met. Conversely, the recursive condition facilitates the repetitive nature of the code. In the context of C++, the recursive function will iterate until the base case is met.
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 structure, a function name (data_type parameter 1….) is defined as 'recursion' and accepts multiple parameters. Within this context, the recursion function invokes itself numerous times.
Simple Example of C++ Recursion
Let's consider a basic illustration to calculate the factorial using 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 instance, we are examining the fact function which recursively invokes itself. Despite reducing the num value by 1 with each invocation, the fact function will yield an output once num falls below 1.
How Recursion Works in C++?
In C++, recursion involves two key components: the Base Case and the Recursion Condition.
1. Base Case:
In C++ recursion, a base class acts as a criterion that facilitates the termination of the process upon fulfillment. It outlines the most basic scenario where the function ceases to invoke itself. The base case determines the moment when the recursion needs to halt, thus averting endless recursion and potential stack overflow. Its primary function is to guarantee that the function attains a conclusive endpoint.
2. Recursive Condition:
In C++, the recursion condition refers to the scenario in which a function invokes itself with an adjusted argument, progressing towards the base case. This mechanism facilitates the iteration of the code.
Types of Recursive Function
There exist primarily two categories of recursive functions. These are outlined below:
- Direct Recursion
- Indirect Recursion
Direct Recursion:
In C++, direct recursion occurs when a function invokes 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's consider a scenario to demonstrate the Fibonacci sequence using simple 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 instance, we are examining a function that calculates Fibonacci numbers using integer input. It employs direct recursion and establishes base cases with conditions like (num==0) and (num==1). The program prompts the user to input a number, initiating a for loop to generate Fibonacci numbers based on the specified condition. Ultimately, the results are displayed in the console.
Indirect Recursion:
In C++, the concept of mutual recursion arises when two or more functions invoke one another in a circular manner.
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 consider an instance where we calculate the factorial of a 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 instance, we are considering two functions: factA(int n) which calculates the factorial by utilizing the factB function, and factB(int n) which calculates the factorial by employing factA. Subsequently, there is an occurrence of indirect recursion as factA(n) invokes factB(n-1), and factB(n) invokes factA(n-1).
Within the main function, the program prompts the user to input a number, then proceeds to invoke the factA(num) function to compute the factorial of the given number. Subsequently, the program displays the result on the console.
C++ Program for Checking a Prime Number Using Recursion
Let's consider an example to verify if a number is prime by employing recursion in the C++ programming language.
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 instance, the primeNum function is a recursive function that invokes itself to determine if the provided number meets the criteria for being a prime number.
Nested Recursion in C++
In C++, nested recursion refers to indirect recursion in which a recursive function initiates another recursive call within its own recursive call. This technique is commonly employed to address intricate mathematical and algorithmic problems.
C++ Nested Recursion Example in C++:
Let's consider an illustration to showcase 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 benefits and drawbacks of recursion in C++ are outlined below:
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 is a contrast between recursion and iteration presented in a tabular format:
| 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
b) Single
#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 is the expected result of the provided C++ code snippet?
#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
