C++ Recursion with example

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

Let's take a simple example to understand this concept.

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.

#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