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 

Advantages & Disadvantages Of Recursion

Advantages of Recursion

  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.

Disadvantages of Recursion

  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.

Frequently Asked Questions

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.

Was this article helpful ?
0 upvotes