Let's Understand Recursion in JS: Types, Time-complexity

Table Of Contents

• What is recursion?
• Head recursion
• Tail recursion
• Tree recursion
• Indirect recursion

What is recursion?

The process in which the function calls itself is called recursion and the responsible function is called the recursion function.

Types of recursion:
On a high level, there are four types

• Head recursion : Here, the recursion function calls itself immediately after checking the base condition and before executing any logic.

function getSquares(n){

    if(n>0){
       getSquares(n-1);
       console.log(n*n);
       return;
    }    
}

getSquares(3)

Output for n = 3 is: 1 4 9

If you notice, we are printing the square of a number and then calling the function by reducing the number by 1.

so you are getting all the squares in ascending order.

But if you write the same logic for the tail recursion you will get the output in descending order. The time complexity of the above code will be O(n+1) i.e. O(n).

• Tail recursion : The recursion function calls itself and the end i.e. after executing all the logic.

function getSquares(n) {

    if (n == 0)
        return;
    print(n * n);
    getSquares(n - 1);
}

getSquares(3)

Output for n=3 is: 9 4 1

The time complexity for this is O(n+1) i.e. O(n).

• Tree recursion: The recursion function calls itself more than one time within the same condition.

function doSomething(n) {
    if (n <= 2)
        return n;
    return doSomething(n - 1) + doSomething(n - 2);
}

console.log(doSomething(5))

Output for n=5 is: 8

If you have noticed in the diagram, we are calling the self function in a tree-like format, that is why we call this type a tree recursion.

The time complexity for this is O(2^(n+1)+1) i.e. O(2^n).

• Indirect recursion : The recursion function A calls the recursion function B and function B calls the recursion function A. So, you can get the point why we call it indirect recursion.

function doSomethingA(n) {
    if (n <= 2)
        return n;
    return doSomethingB(n - 1)
}

function doSomethingB(n) {
    if (n <= 2)
        return n;
    return doSomethingA(n - 1)
}

console.log(doSomethingA(5))

Output for n=5 is: 2

To be honest there is not much logic in this example, I have taken this example just to explain you the concept.

if you notice we are calling doSomethingA() and doSomethingA is calling doSomethingB() function and further doSomethingB is calling doSomethingA() function.

This type of recursion calling is called the indirect recursion.

Question for you:
Try to calculate time complexity for indirect recursion. if you have any doubt about it or don't understand any point, you can ask by writing a comment, and I'll try to resolve it with an explanation.