Recursion is a process in which a function calls itself directly or indirectly to solve a problem. In this article, we will learn Recursion in C++ and its implementation.
Syntax:
int fun() { .... fun() }
Recursion allows the function to repeat a specific action until a specific condition is met and the function stops calling itself when the specific condition is met that stopping condition is also known as the base condition.
Let's understand recursion with one standard example: finding the factorial of a given number.
C++ Program to find the Factorial of a number.
#include<iostream> using namespace std; //function to find factorial int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); } int main() { int num; cout<<"Enter a number: "; cin>>num; cout<<"Factorial of given number: "<<factorial(num); return 0; }
Enter a number: 5
Factorial of given number: 120
Working of Recursion.
In the above example, the factorial function calculates the factorial of n by making a recursive call to itself with n-1 as the argument. The if statement checks for the base case, which is when n is equal to 0 and returns 1 in that case. When the base case is not reached, the function calculates n * factorial(n-1), and this continues until the base case is reached.
 |
| Recursion |
We need to follow two simple steps to solve any recursion problem and these are:
Step 1: Divide the problem into smaller sub-problem.
Finding the solution for a smaller sub-problem is easy compared to finding the solution for a single large problem. In recursion, we keep dividing the problem into smaller sub-problem until we find the smallest sub-problem.
Step 2: Specify the base condition to stop the recursion.
The base condition is the one that doesn't require calling the same function again and it helps in stopping the recursion. In our case, finding the factorial of 0 is the base case.
Types of Recursion.
- Direct Recursion
- Indirect Recursion
- Tail Recursion
- Non-Tail Recursion
1. Direct Recursion.
Direct recursion is a condition in which the function calls itself directly from the inside.
//Example of direct Recursion void fun() { //some code fun(); }
2. Indirect Recursion.
Indirect recursion is a condition in which the first function calls the second function and the second function again calls the first function.
//Example of indirect Recursion void fun_1() { //some code fun_2(); } void fun_2() { //some code fun_1(); }
3. Tail Recursion.
A recursion function is said to be a tail recursion if the recursion call is the last thing done by the function. There is no need to keep a record of the previous state.
Example:
//Example of Tail Recursion in C++ #include<iostream> using namespace std; //recursive function int fun(int n) { if(n == 0) return 0; else cout<<n<<" "; return fun(n - 1); } int main(){ //function call fun(3); return 0; }
Output:
3 2 1
4. Non-Tail Recursion.
A recursion function is said to be non-tail recursion when the same function call is not the last thing done by the function. After returning back there is some statement left to evaluate.
Example:
//Non-Tail Recursion Example in C++ #include<iostream> using namespace std; void fun(int n) { if(n == 0) return; fun(n - 1); cout<<n<<" "; } int main() { //function call fun(3); return 0; }
Output:
1 2 3
Conclusion.
- Every recursion program can be written as iterative.
- Every recursion program can be modeled into an iterative program but recursive programs are more elegant and require relatively fewer lines of code.
- The recursive program requires more space in memory than iterative programs.
