Recursive Functions concept in C++
A recursive function in the C++ programming language is a user-defined recursion function that automatically calls itself to solve a specific programming problem. Recursion is a powerful technique used in C++ and other programming languages. Recursion involves breaking a complex problem into smaller sub-problems or modules, and the custom-declared function automatically calls itself multiple times with these smaller sub-instance modules until it reaches a base case, a proper solution to the problem being handled. This provides an easy modular solution to the smallest sub-problem.
Key concepts and features of recursive functions in the C++ programming language.
Recursive case in recursion.
This is an important part of a recursive function, where the recursive function automatically calls itself to solve small module instances of a problem.
Base Case in Recursion.
This is the simplest instance method of a recursive function problem, which does not require the user to call the recursive function further. It stops the recursion process step by step, and provides an output for the smallest recursive sub-problem.
Function Call Stack Recursion in C++.
When a recursive function is called in a program, the recursive function’s local variables and state are automatically saved on the call stack. Each recursive function adds a new frame to the call stack. Once the base case is reached in the function call stack method, the recursion function “unwinds” control by returning it to the previous function call, and finally, the function call stack displays the recursive function’s final result after solving it.
Structure of a recursive function in C++.
The structure of a recursive function in the C++ programming language typically looks like this.
return_type function_name(parameters) {
// Base case: A simple condition to stop the user-defined recursion function.
if (/* User-defined base case condition */) {
return /* Recursion function base case value */;
}
// Recursive case: This recursively calls the recursion function.
return function_name(/* Recursion modular small problem */);
}
Element of a recursion function.
- Recursive call – A user-defined recursion function calls itself with a modified or small modular input.
- Base case – In a recursive function, recursion continues until it reaches the base case value. After that, it begins returning the recursion value.
- Unwinding – Once a recursive function hits its base case, the recursion automatically “unwinds,” and each recursive call returns to the previous level until it reaches the starting call.
Example of a factorial calculation recursive function.
The simplest example of recursion in C++ programming is calculating the factorial value of a number. This is defined in C++ programming as follows.
n!=n×(n−1)×(n−2)×⋯×1
n!=n×(n−1)×(n−2)×⋯×1
The recursive definition of a factorial value in C++ is as follows.
- Base case – 1!=11!=1
- Recursive case – n!=n×(n−1)!n!=n×(n−1)!
Example of the factorial recursive function in C++.
#include <iostream>
using namespace std;
// here we define a Recursive function to find out a factorial value of given number
int fact(int n) {
// Base case: here it calculates a factorial of 0 or 1 is 1
if (n <= 1) {
return 1;
}
// Recursive case: here it calculates n * factorial(n-1) value
return n * fact(n – 1);
}
int main() {
int integer;
cout << “Enter a desire integer value – “;
cin >> integer;
cout << “The Factorial of the given integer value ” << integer << ” is – ” << fact(integer) << endl;
return 0;
}
Explanation of factorial recursive function.
Here in this program, the fact() function calls itself with n-1 values until it reaches the base case factorial value (n <= 1). After that, it starts returning the factorial value. When the function is called, the fact(7) value is returned. So it calculates 7 * factorial(6), and in the same sequence fact(5) finds out the value 5 * fact(4), and so on until fact(1) returns 1. Then, all the factorial values are multiplied together, and finally the final factorial value is returned. This automatically terminates the repetition process sequence of the factorial function.
Recursive Fibonacci series concept in C++.
Let’s learn in detail how to print a recursive Fibonacci series with a recursive function in C++ programming with an example.
The recursive relation is.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
Fibonacci series base case.
if (n <= 1)
return n;
The recursion stops here.
fibonacci(0) = 0
fibonacci(1) = 1
Fibonacci series recursive case.
return fibonacci(n – 1) + fibonacci(n – 2);
Fibonacci Every number is the sum of the previous two.
F(n)=F(n−1)+F(n−2)+F(n−3)+F(n−4)
Recursive Fibonacci series example in C++.
#include <iostream>
using namespace std;
int fibonacci_series(int p) {
if (p <= 1)
return p;
return fibonacci_series(p – 1) + fibonacci_series(p – 2);
}
int main() {
int p;
sin >> p;
for (int q = 0; q < p; q++) {
cout << fibonacci_series(q) << ” “;
}
return 0;
}
