# Recursion

RAJESH RUNIWAL
Last Updated: May 21, 2022

## Introduction:

Recursion is the method in which a function calls itself as its subroutine, which will solve a complex iterative problem by dividing it into sub-tasks. Any function which calls itself recursively is called recursive function, and the method of calling a function by itself is called Recursion. Recursion results in several iterative calls to the same function. However, it is essential to have a base case to terminate the Recursion.

## Types of Recursion

Broadly, there are two types of recursion based on how the recursive function is called.

1. Direct recursion

2. Indirect recursion

## Direct Recursion

When a function calls itself directly is known as a direct recursive function is called direct Recursion.

### Syntax

``````void directRecursionFunction()
{
// some code…

directRecursionFunction();

// some code...
}``````

### Example

``````#include <iostream>
using namespace std;

int square(int x)
{
if (x == 0)
{
return x;
}

else
{
return square(x-1) + (2*x) - 1;
}
}
int main()
{
int input=30;
cout << input<<"^2 = "<<square(input);
return 0;
}``````

Output

``30^2 = 900``

## Indirect Recursion

When a function calls itself indirectly from another function, this function is called indirect recursive, and this type of Recursion is said to be indirect Recursion.

### Syntax

``````void indirectRecursionFunctionf1();
void indirectRecursionFunctionf2();

void indirectRecursionFunctionf1()
{
// some code...

indirectRecursionFunctionf2();

// some code...
}

void indirectRecursionFunctionf2()
{
// some code...

indirectRecursionFunctionf1();

// some code...
}``````

### Example

``````#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 ``

1. Less number code lines are used within the recursion program, and consequently, the code appears shorter and cleaner.
2. Recursion is a simple technique to solve the problems involving data structure and algorithms like graph and tree
3. Recursion enables to reduce the time complexity
4. It facilitates the reduction of the useless calling of a function.
5. The Recursion is the quality approach to define objects that have repeated structural forms.

1. It consumes lots of stack area
2. It takes greater time to procedure the program
3. If an error is accrued inside the program, it is difficult to debug the error in comparison to the iterative program.

1. What is the Fibonacci Series? Write the code?

Fibonacci number series is the sequence of all numbers such that every number is the sum of the two preceding ones beginning from zero(0) and one(1).

``````#include <iostream>
using namespace std;
int fibonnaci(int x) {
if((x==1)||(x==0)) {
return(x);
}else {
return(fibonnaci(x-1)+fibonnaci(x-2));
}
}
int main() {
int x , i=0;
cout << "Enter the number of series: ";
cin >> x;
cout << "\nFibonnaci Series : ";
while(i < x) {
cout << " " << fibonnaci(i);
i++;
}
return 0;
}``````

Output

``````Enter the number of series: 5
Fibonnaci Series : 0 1 1 2 3 ``````

Check out this video to understand the implementation of Fibonacci Series better

2. Write a Factorial Program by Using Recursion In C++?

``````#include <iostream>
using namespace std;

int fact(int n);

int main()
{
int n;

cout << "Enter a positive integer: ";
cin >> n;

cout << "Factorial of " << n << " = " << fact(n);

return 0;
}

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

Output:

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

Check out this video to understand the implementation and logic of factorial program.

3. Write a code of Reverse A Number Using Recursion In C++?

``````#include <iostream>
using namespace std;

void reverseNumber(int n)
{
if (n ==0)
{
return;
}
else
{
cout<<n % 10;
reverseNumber(n/10);
}
}

int main()
{
int n, reverse;
cout<<"Enter number ";
cin >> n;
cout<<"Reverse number is ";
reverseNumber(n);
return 0;
}

``````
``````Output
Enter number 6543
Reverse number is 3456``````

## Key Takeaways

In this blog, we learned about how to use the Recursion and the type of Recursion mostly, even though the recursion approach consumes a lot of memory storage due to the use of stack data structure. It is used to solve various problem statements to reduce the program's time complexity and lines of code. If you wish to prepare for technical interviews, you can visit our library of curated articles and blogs by clicking here.