C++ Recursion

# C++ Recursion

## Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Recursion has got a problem-solving tool, where it dives the larger problems into simple tasks and wirking out individually to follow an individual sequence.

## Syntax of Recursion Function

The general syntax of the recursion function in C++ is given as:

```return type function name([arguments])
{
Body of the statements;
function name ([actual arguments])        // recursive function
}```

## Working of Recursion in C++

``````void recurse()
{
... .. ...
recurse(); // function calls itself
... .. ...
}

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

Working

• Recursion performs repetition on the function calls, and it stops the execution when the base case becomes true.
• In Simple words, The recursion continues until some condition is met.
• A base case condition should be defined in the recursive function to avoid stack overflow errror messages.
• If no base case is defined it leads to infinite recursion.
• To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call and the other doesn't.

### Example 1: Factorial of a Number Using Recursion

``````// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int fact(int);

int main() {
int num, result;

cout << "Enter positive number: ";
cin >> num;

result = fact(num);
cout << "Factorial of " << num << " = " << result;
return 0;
}

int fact(int num) {
if (num > 1) {
return num * fact(num - 1);
} else {
return 1;
}
}``````

Output

```Enter a positive number: 5
Factorial of 5 = 120```

### Working of Factorial Program

As we can see, the `fact()` function is calling itself. However, during each call, we have decreased the value of num by `1`. When num is less than `1`, the `fact()` function ultimately returns the output.

## Types of recursion

There are two types of recursion

1. Direct recursion
2. Indirect recursion

## Direct recursion

Direct recursion : When function calls itself, it is known as direct recursion.

The example, we have seen above is a direct recursion example.

## Indirect recursion

Indirect recursion : When function calls another function and that function calls the calling function, then this is known as Indirect recursion.

For example : Function A calls function B and function B calls function A.

### Example 2: Find Factorial using Indirect recursion

``````// Factorial of n = 1*2*3*...*n
#include <iostream>
using namespace std;

int factA(int);
int factB(int);

int factA(int n){
if (n <= 1) {
return 1;
} else {
return  n * factB(n - 1);
}
}

int factB(int n){
if (n <= 1) {
return 1;
} else {
return  n * factA(n - 1);
}
}

int main() {
int num;

cout << "Enter positive number: ";
cin >> num;

cout << "Factorial of " << num << " = " << factA(num);
return 0;
}``````

Output

```Enter a positive number: 5
Factorial of 5 = 120```

• It makes our code shorter and cleaner.
• Recursion is required in problems concerning data structures and advanced algorithms, such as Graph and Tree Traversal.

• It takes a lot of stack space compared to an iterative program.
• It uses more processor time.
• It can be more difficult to debug compared to an equivalent iterative program.

## Next Tutorial

We hope that this tutorial helped you develop better understanding of the concept of Recursion in C++.

Keep Learning : )

In the next tutorial, you'll learn about C++ `Return by Reference`.