Performance Of Recursion Vs Loop Using JavaScript

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, 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 of 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.