In this tutorial, you will learn about the recursion function C++ language and how to use it with the help of examples.
In C++ you can use a technique called recursion where you specify a base case and then you recursively call the same function till it exits through the base case to solve the problem. The problems and challenges which can be solved using a looping statement can also be done by recursion.
The only benefit is that the code becomes simpler and smaller with increased time complexity. So when you need to consider time complexity, looping is your method, or else you should use recursion to solve the problem.
C++ Recursion Syntax
The syntax of the C++ recursion is as follows.
return_type function_name( arg1_type arg1_name, ... )
{
//Base Case
//Recursive Call to itself`
}
C++ Recursion Example
The following code demonstrates how to print all the numbers from 1 to 3 which can also be done using a simple for loop but here we will be using recursion to do it.
// A C++ program to demonstrate working of recursion
#include <iostream>
using namespace std;
void printFun(int test)
{
if (test < 1) // Base Case
return;
else {
printFun(test - 1); // Recursive Call
cout << test << " ";
return;
}
}
// Driver Code
int main()
{
int test = 3;
printFun(test);
}
Output
Example 2: Fibonacci Series
The Fibonacci series is a series where the first and second elements are 0 and 1 respectively. The following elements are the sum of the previous two. Hence a recurrence relation can be established by :
T(n) = T(n-1) + T(n-2)
The following code prints the Fibonacci series using recursion.
// A C++ program to print fibonacci by using recursion
#include <iostream>
using namespace std;
int fib(int n)
{
// Stop condition
if (n == 0)
return 0;
// Stop condition
if (n == 1 || n == 2)
return 1;
// Recursion function
else
return (fib(n - 1) + fib(n - 2));
}
// Driver Code
int main()
{
// Initialize variable n.
int n = 5;
cout<<"Fibonacci series of 5 numbers is: ";
// for loop to print the fiboancci series.
for (int i = 0; i < n; i++)
{
cout<<fib(i)<<" ";
}
return 0;
}
Output
Example 3: Factorial of a number
The Factorial of a number is the product of all the numbers from 1 to n. Hence a recurrence relation can be established by :
T(n) = n*T(n-1)
The following code prints the Fibonacci series using recursion.
// A C++ program to print Factorial by using recursion
#include <iostream>
using namespace std;
int f(int n)
{
// Stop condition
if (n == 0 || n == 1)
return 1;
// Recursive condition
else
return n * f(n - 1);
}
// Driver code
int main()
{
int n = 5;
cout<<"factorial of "<<n<<" is: "<<f(n);
return 0;
}