The process in which a function calls itself is known as recursion and the corresponding function is called the **recursive function**. The popular example to understand the recursion is factorial function.

**Factorial function:** f(n) = n*f(n-1), base condition: if n<=1 then f(n) = 1. Don’t worry we wil discuss what is base condition and why it is important.

In the following diagram. I have shown that how the factorial function is calling itself until the function reaches to the base condition.

Lets solve the problem using C++ program.

## C++ recursion example: Factorial

#include <iostream> using namespace std; //Factorial function int f(int n){ /* This is called the base condition, it is * very important to specify the base condition * in recursion, otherwise your program will throw * stack overflow error. */ if (n <= 1) return 1; else return n*f(n-1); } int main(){ int num; cout<<"Enter a number: "; cin>>num; cout<<"Factorial of entered number: "<<f(num); return 0; }

**Output:**

Enter a number: 5 Factorial of entered number: 120

### Base condition

In the above program, you can see that I have provided a base condition in the recursive function. The condition is:

if (n <= 1) return 1;

The purpose of recursion is to divide the problem into smaller problems till the base condition is reached. For example in the above factorial program I am solving the factorial function f(n) by calling a smaller factorial function f(n-1), this happens repeatedly until the n value reaches base condition(f(1)=1). If you do not define the base condition in the recursive function then you will get stack overflow error.

## Direct recursion vs indirect recursion

**Direct recursion:** When function calls itself, it is called direct recursion, the example we have seen above is a direct recursion example.

**Indirect recursion:** When function calls another function and that function calls the calling function, then this is called indirect recursion. For example: function A calls function B and Function B calls function A.

### Indirect Recursion Example in C++

#include <iostream> using namespace std; int fa(int); int fb(int); int fa(int n){ if(n<=1) return 1; else return n*fb(n-1); } int fb(int n){ if(n<=1) return 1; else return n*fa(n-1); } int main(){ int num=5; cout<<fa(num); return 0; }

**Output:**

120

Raza says

October 18, 2017 at 11:04 AMNice Example!

I have one question, when the base condition is reached, shouldn’t the function return ‘1’ to main call rather the result accumulated i.e ‘120’?

Shadow3641 says

April 17, 2018 at 11:14 PMNo, because it queues up the multiplier from the first function call of the n*f(n-1). So when n is finally <= 1 it returns it to the function call before. So instead of n* f(n-1), it would be n * 1. From here it would have all the previous values of n stored and solve the equation.