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

Nice 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

No, 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.