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.

Table of Contents

*What is recursion?*

*What is recursion?*

Any function which calls itself is called ** recursive** and the process is called

**. The calls in recursion are of two types**

*recursion***and**

*direct*

*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

**. Otherwise, recursive calls will not end and finally the**

*terminating condition***will occur.**

*buffer overflow**Why recursion?*

*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***, etc.**

*Searching and Sorting**Format of Recursive function*

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

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

*Direct calls**Indirect calls*

*Direct recursion*

*Direct recursion*

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

- Tail recursion
- Head recursion
- Tree recursion
- Nested recursion

*Tail recursion*:

*Tail recursion*

When a function calls ** itself **and the

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

*call is the last statement*** 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

**time hence the**

*O(1)***is**

*time complexity*

*O(N).*** Space complexity for tail recursion**:

**, since there are N recursive calls hence maximum N memory blocks will be allocated at any point of time. Therefore,**

*O(N)***space complexity**is

**.**

*O(N)*** Note:** The

**and**

*time complexity***discussed above is of the example we have taken above. Both can vary from example to example.**

*space complexity***Head recursion**:

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

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

**time hence the**

*O(1)***is**

*time complexity*

*O(N).*** Space complexity for tail recursion**:

**, since there are N recursive calls hence maximum N memory blocks will be allocated at any point of time. Therefore,**

*O(N)***space complexity**is

**.**

*O(N)**Tree recursion*

*Tree recursion*

This is similar to ** Linear recursion**. In

**function calls itself only one time whereas in**

*Linear recursion***a function calls itself more than**

*Tree recursion***. Let’s see an example on**

*once***.**

*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

**. Therefore, the**

*1, 2, 4, 8, 16……2^N***of the above example is**

*time complexity***.**

*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

**Hence the space complexity is**

*N*.**.**

*O(N)**Nested recursion*

*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

**. Let’s see an example.**

*“recursion inside recursion”*```
#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*

*Indirect Recursion*

- The name itself suggests, calling someone
. In this recursion, there may be more than one function*indirectly*in a*calling one another*.*circular fashion* - Suppose we have two functions
and*A()*,*B()*calls*A()*and*B()*calls*B()*, and thus it makes a cycle.*A()* - We should be very careful with the base case conditions while implementing
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.*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

**, the**

*indirect recursion***concept has used.**

*forward declaration** Forward declaration*

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

*Conclusion*

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