Performance Of Recursion Vs Loop Using JavaScript

This is a blog comparing the performance of recursion with looping technique for the same algorithm.

Introduction

 

Today, we are going to compare the performance of Recursion algorithms and Loops.

 

In layman's terms, Recursion is a process of doing something again and again. Similarly, in JavaScript, the Recursion algorithm is used to call the same method inside the method to get the result. It increases the readability of the algorithm. Let's check if it is performance friendly or not !!!

 

Example

 

I am going to write a code to calculate the power of any number. I will be implementing the algorithm using both, Loop and Recursion to check the performance of the algorithms.

function powUsingLoop(x, n) {
    var result = 1;
    for (var i = 0; i < n; i++) {
        result *= x;
    }
    return result;
}

function powUsingRecursion(x, n) {
    if (n == 1) {
        return x;
    } else {
        return x * powUsingRecursion(x, n - 1);
    }
}

I have created 2 functions both of which take 2 arguments. In the first function, I have implemented Looping concepts and in the second one, I have used the Recursion concept. I will be calling both of the functions now.

 

I will be using console.time to calculate the time of execution.

 

Let's check with small numbers to see if it works perfectly.

console.time("looping #1");
console.log(powUsingLoop(2,3));
console.timeEnd("looping #1");
console.time("Recursion #1");
console.log(powUsingRecursion(2,3));
console.timeEnd("Recursion #1");

Output

 

8

looping #1: 8.000244140625ms

8

Recursion #1: 0.999755859375ms

 

This says that the 2 power 3 is 8. This is the output in both the functions. But you can see the time difference. For looping, it took 8ms whereas, in Recursion, it got executed in less than 1ms.

 

Let's increse the numbers !!

console.time("looping #2");
console.log(powUsingLoop(2,1000));
console.timeEnd("looping #2");
console.time("Recursion #2");
console.log(powUsingRecursion(2,1000));
console.timeEnd("Recursion #2");

Output

 

1.0715086071862673e+301

looping #2: 11.000244140625ms

1.0715086071862673e+301

Recursion #2: 1ms

 

Looping method took 11ms to complete the evaluation whereas it took just 1ms for Recursion.

 

Let's increase the numbers again.

console.time("looping #3");
console.log(powUsingLoop(2,10000));
console.timeEnd("looping #3");
console.time("Recursion #3");
console.log(powUsingRecursion(2,10000));
console.timeEnd("Recursion #3");

Output

 

Infinity

looping #3: 13ms

 

Uncaught RangeError: Maximum call stack size exceeded

 

Surprised!!!

 

For looping, it got executed successfully with output as Infinity.

 

But for Recursion, it got errored out. This is because once you call recursion it adds up all the function calls to the call stack and finally it exceeds the limit. There is stack size or memory exhaustion per browser which ensures the number of calls that can be present in a stack at any point in time.

 

Conclusion

 

Recursion is less time consuming compared to Looping in most of the cases. But there should be a breaking condition in place for the Recursion functions to ensure it should not exceed the call stack limit to error-out.

 

Please try out the same example here.