Recursion in C++
Recursion in C++ Programming
In this page, we have explained all about recursion in C++ program which includes the different types of recursion in C++.
What is Recursion in C++?
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. A recursive function is a function that calls itself with a smaller input until it reaches a base case, at which point it returns a result.
Example of a recursive function in C++ that calculates the factorial of a given number:
Run
#include <iostream>
using namespace std;
int factorial(int n)
{
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
int main()
{
int num;
cout << "Enter a number: "; cin >> num;
int result = factorial(num);
cout << "The factorial of " << num << " is " << result << endl;
return 0;
}
Output
Enter a number: 7 The factorial of 7 is 5040
Note
The function factorial calculates the factorial of a given number n by calling itself with n - 1 until it reaches the base case of n == 0, at which point it returns 1. This is an example of a tail-recursive function, which means that the recursive call is the last thing the function does before returning a value. Tail-recursion can be optimized by the compiler, so it is generally preferred over non-tail-recursive functions.
Types of Recursion
There are two main types of recursion in C++:
- Tail recursion
- Non-tail recursion
Tail Recursion
- This is a type of recursion where the recursive call is the last thing the function does before returning a value.
- Tail-recursive functions are generally preferred over non-tail-recursive functions because they can be optimized by the compiler.
int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Non Tail Recursion
- This is a type of recursion where the recursive call is not the last thing the function does before returning a value.
- Non-tail-recursive functions are generally less efficient than tail-recursive functions because they cannot be optimized by the compiler.
int factorial(int n) {
if (n == 0) {
return 1;
}
int result = factorial(n - 1);
return n * result;
} Program to calculate the nth number in the Fibonacci sequence using Recursion
Run
#include <iostream>
using namespace std;
int fibonacci(int n)
{
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci (n - 1) + fibonacci (n - 2);
}
int main()
{
int num;
cout << "Enter a number: ";
cin >> num;
int result = fibonacci(num);
cout << "The " << num << "th number in the Fibonacci sequence is " << result << endl;
return 0;
}
Output
Enter a number: 13 The 13th number in the Fibonacci sequence is 233
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment