DEV Community

Cover image for Let's Understand Recursion in JS: Types, Time-complexity
Dnyaneshwar Dhakane
Dnyaneshwar Dhakane

Posted on

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

Table Of Contents

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Tree Recursion

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

console.log(doSomething(5))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)