C++ Recursion

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

1 2 3

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

Fibonacci series of 5 numbers is: 0 1 1 2 3

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;
}

Output

factorial of 5 is: 120

Please get connected & share!

Advertisement