C++ Recursion

In this tutorial, we are going to learn about recursion in C++.

A Recursive function is a specialised function which capable of calling itself during its execution. And, this process is known as recursion. Using recursion many of the tough problems in programming can be solved easily.

Let’s see more about it.

---

How it Works?

The following code represents layout of a program consisting of recursive function.

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
    ... .. ...
}

int main()
{
    ... .. ...
    ... .. ...
    recurse();
    ... .. ..
}

Above figure represents the difference between function call and recursive call.

A recursive function keeps calling itself until a certain condition is satisfied.

Let’s take an example for better understanding of the topic.

Example 1:

One of the best example to understand recursion is factorial program.

The following program prints factorial of a non negative number given by user.

#include <iostream> 

using namespace std; 

int factorial(int n) { 
    if (n > 1) { 
        return n * factorial(n - 1); 
    } 
    else { 
        return 1; 
    } 
}

int main() {
    int n, result;

    cout << "Enter a non-negative number: ";
    cin >> n;

    result = factorial(n);

    cout << "Factorial of " << n << " is " << result;

    return 0;
}

Output :

Enter a non-negative number: 5
Factorial of 5 is 120

# Explanation :

Above figure represents the working of function factorial().

---

Pros of C++ Recursion

• Recursion reduces the code complexity and hence code much simple and readable.
• Recursion is required in problems of data structures and advanced algorithms, such as Graph and Tree Traversal.
• Recursion makes debugging lot more easier, as complexity is reduced.

---

Cons of C++ Recursion

• Recursion takes more space as compared other iterative techniques.
• It uses more processor time.