Why is recursion faster than iteration in JS?

user_709040 0
Viewed 756

I've been doing JS problems on LeetCode and noticed that the recursive solutions run faster than the iterative solutions in almost every case (ex. DFS with a stack vs recursion).

I looked online and found a couple of blog posts that came to similar conclusions around performance. https://www.c-sharpcorner.com/blogs/performance-of-recursion-vs-loop-using-javascript

The Oreily book, like most formal material on the subject, states that iteration is more performant because of the "lower overhead" which I understand but then why isn't that the case in practice? https://www.oreilly.com/library/view/high-performance-javascript/9781449382308/ch04.html

I do see that recursion can fail at particularly large stack sizes but it always seems to be more performant than iteration. What's going on? I saw that TCO hasn't been implemented in JS so I'm very confused.

recursion javascript
1 Answers

Well, to understand recursion over iteration (or vice versa), we need to understand how both technique works.

What is recursion?

  1. It's function calling it self. so number of calls take place, number of times the properties of function (which includes variables, data-structures, sub-functions that the main function uses, will recreate over and over again). and at the end, compiler or (JIT in case of JavaScript) must face some overheads.

  2. And the process will continue until/unless base case have found, in this case all overheads during recursion will release.

  3. In case, if base-case not found/matched all the stack-frame which was allocated for this particular function will be exhausted, and we will get some thing like: Maximum call stack size exceeded

What is Iteration?

  1. As the name suggest, it's a repetitive instruction which will perform some operation given by the coder.
  2. In compare to Recursion, no other stack-frame will be used without main-stack-frame. and all the properties of the function will be reinitialised with new value over and over again.

Based on the comparison i have made, you can clearly get an idea, which is more and which is less efficient to Compiler or to JIT. (and it is generalised to every language you will work on).

Now coming to the performance, the article link which you provided clearly not showing accurate measurements of all the scenarios. The time to execute a function clearly and mainly depends on the number of instruction the function performs.

Looking at the following snippets you can re-think about the conclusion you have so far:

function nthFibo(a){
    if(a <= 2){
        return a;
    }else{
        return nthFibo(a-1)+nthFibo(a-2);
    }
   }


console.time("looping #1");  
console.log(nthFibo(45));
console.timeEnd("looping #1");

and also check the time required for iteration, which will give you same output as recursion gave:

function nthFiboIterative(a){
    var first = 0, second = 1;
    var result = 0;
    var i = 1;
    while(i ++ <= a){
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

console.time("looping #2");  
console.log(nthFiboIterative(45));
console.timeEnd("looping #2");

But this is not a fair test as our first program creates an exponential process that we compare to a linear process in the second program. Let's see a recursive nthFibo that evolves a linear iterative process -

function nthFibo (a, x = 1, y = 1)
{ if (a == 0)
    return x;
  else
    return nthFibo(a - 1, y, x + y)
}

console.time("looping #3");  
console.log(nthFibo(45));
console.timeEnd("looping #3");

It's important to know the distinction between process and a procedure (function). A recursive function can evolve a recursive process, an exponential process, or an iterative process. Similarly, a non-recursive function can evolve an iterative process (think simple for loop) or an exponential process (think something like Ackerman function).

user_83596230
Related