1.
Introduction:
2.
Types of Recursion
3.
Direct Recursion
3.1.
Syntax
3.2.
Example
4.
Indirect Recursion
4.1.
Syntax
4.2.
Example
5.
5.1.
5.2.
6.
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Recursion

RAJESH RUNIWAL
Basics of C++
Free guided path
9 chapters
99+ problems

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

Also see, Literals in C, Fibonacci Series in C++

## Types of Recursion

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

1. Direct recursion

2. Indirect recursion

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

You can try by yourself with the help of online c++ compiler.

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

Must Recommended Topic, procedure call in compiler design

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