Types of recursion | Direct And Indirect Recursion

Here we will be discussing the different types of recursive calls but before we dive into the types of recursive calls, let’s revise the basic concepts of recursion.

What is recursion?

Any function which calls itself is called recursive and the process is called recursion. The calls in recursion are of two types direct and indirect.

A recursive method solves the problem by calling a copy of itself to work on a smaller problem this is called the recursion step.

The function can perform any type of operation while calling but should perform anything at returning.

NOTE: It is very important to ensure that the recursion must have a terminating condition. Otherwise, recursive calls will not end and finally the buffer overflow will occur.

Why recursion?

Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code.

Many important algorithms are based on recursion Dynamic Programming, Graph Algorithms, Divide and Conquer, Searching and Sorting, etc.

Format of Recursive function

if(terminating condition or base case)
 {
      return some base case value
 }
 else if(terminating condition 2 or base case 2)
 {
     return some base case value
 }
 .
 .
 .
 else
 {
     recursive call 1
     recursive call 2
     recursive call 3
     .
     .
     .
     return value
 }

Recursion and Memory

Each recursive call makes a new copy of that method ( actually only the variables) in memory. Once the method ends (that is, return some data), the copy of that returning method is removed from memory.

Now let’s look at the different types of recursive calls. There are mainly two types of recursive calls.

  1. Direct calls
  2. Indirect calls

Direct recursion

When a function calls itself from within itself then this is called direct recursion. Direct recursion is further divided into 4 types.

  1. Tail recursion
  2. Head recursion
  3. Tree recursion
  4. Nested recursion

Tail recursion:

When a function calls itself and the call is the last statement in the function then the recursion is said to be tail recursion. Before the recursive call, the function can perform any number of statements. Let’s see an example.

types of recursion
Tail recursion

example:

Print values in descending order using recursion.

// Tail recursion
#include<bits/stdc++.h>
using namespace std;
// Recursive funciton
 void fun(int n)
 {
     if(n<0)
     {
         return ; 
     }
     cout<<n<<" ";

     fun(n-1); // last statement is a recursive call
 }
//driver code
 int main()
 {
     int n = 5;
     fun(n);
     return 0;
 }

Since the last statement that has executed is the recursive call and no further statement has executed after the call. Also, nothing has returned from the function. Therefore, this recursion is called tail recursion.

Time complexity for tail recursion: O(N), since there are N recursive calls and each call takes O(1) time hence the time complexity is O(N).

Space complexity for tail recursion: O(N), since there are N recursive calls hence maximum N memory blocks will be allocated at any point of time. Therefore, space complexity is O(N).

Note: The time complexity and space complexity discussed above is of the example we have taken above. Both can vary from example to example.

Head recursion:

After the base condition if the first statement is the recursive call i.e all the operations are being written after the recursive call then this said to be Head recursion. There’s no operation, no statement before the recursive call. Let’s see an example.

types of recursion
Head recursion

example:

print the first N values in ascending order using recursion.

#include<bits/stdc++.h>
using namespace std;
//recursive function
void fun(int n)
{
    if(n<0) // base condition
    {
         return ; 
    }
    fun(n-1); // first statement is recursive call 
    cout<<n<<" "; // operation after recursive call
}
//drvier code
int main()
{
    int n = 5;
    fun(n);
}

This is an example of head recursion. The first statement after the base condition is a recursive call and the rest of the operations have executed after the recursive call, not before it.

Time complexity for tail recursion: O(N), since there are N recursive calls and each call takes O(1) time hence the time complexity is O(N).

Space complexity for tail recursion: O(N), since there are N recursive calls hence maximum N memory blocks will be allocated at any point of time. Therefore, space complexity is O(N).

Tree recursion

This is similar to Linear recursion. In Linear recursion function calls itself only one time whereas in Tree recursion a function calls itself more than once. Let’s see an example on tree recursion.

#include<bits/stdc++.h>
 using namespace std;
  //recursive function
  void fun(int n)
  {
      if(n>0) // base condition
      {
        cout<<n<<" "; 
        fun(n-1);// first call  
        fun(n-1);// second call
      }
  }
  //drvier code
  int main()
  {
      int n = 3;
      fun(n);
  }

Here the function calls itself twice i.e fun(n-1) and fun(n-1).

Time complexity for Tree recursion: Here if we observe carefully then we will find that at each level the number of nodes is getting twice compared to the previous level i.e 1, 2, 4, 8, 16……2^N. Therefore, the time complexity of the above example is O(2^N).

Space complexity for Tree recursion: The maximum depth of the tree is proportional to the space complexity. Here, the maximum depth of the tree is N. Hence the space complexity is O(N).

Nested recursion

When a function makes a recursive call and in that call, the parameter it passes is also a recursive call then this recursion is called Nested recursion. That means “recursion inside recursion”. Let’s see an example.

#include<bits/stdc++.h>
 using namespace std;
  //recursive function
  int fun(int n)
  {
      if(n>10) // base condition
      {
        return n;
      }
      // carefully observe this the recursive call has a parameter which is also a //recursive call
      return fun(fun(n+5));
 }
  //drvier code
  int main()
  {
      int n = 0;
      cout << fun(n);
  }

Indirect Recursion

  1. The name itself suggests, calling someone indirectly. In this recursion, there may be more than one function calling one another in a circular fashion.
  2. Suppose we have two functions A() and B(), A() calls B() and B() calls A(), and thus it makes a cycle.
  3. We should be very careful with the base case conditions while implementing indirect recursion because the body of the function keeps jumping back and forth and, to end the indirect recursion all the functions’ base condition should be reached.
types of recursion
Cycle made in indirect recursion

Let’s see an example of this recursion.

#include<bits/stdc++.h>
 using namespace std;

  void A(int n);// forward declaration

  void B(int n)
  {
      if(n > 0)
      {
          cout<< n<<" ";
      A(n/2);  }
 }
  void A(int n)
  {
      if(n > 0)
      {
          cout<< n<<" ";
      B(n/2);  }
 }
  //drvier code
  int main()
  {
      int n = 100;
      A(n);
  }

Note: In indirect recursion, the forward declaration concept has used.

Forward declaration

Forward declaration is an important concept in this we declare the functions or classes at the top so that other functions that are defined after them can call and use them. Here the function A() has forwardly declared.

Today, we have discussed the types of recursion and their implementation. Let’s see the conclusion of this article.

Conclusion

  • It totally depends on the user which type of recursion i.e direct or indirect user wants to use in their code.
  • Recursion is the root of many advanced algorithms like Dynamic Programming, Graph Algorithms, Searching and Sorting, etc.
  • In programming, programmers prefer direct recursion over indirect recursion.
  • Direct recursion is easy to write and handle compared to indirect recursion.

2 Comments

  1. Bro it’s really helpful, before this article i don’t even know how many types of recursion exist.. thanks bro and post more articles..

Leave a Comment

Your email address will not be published. Required fields are marked *