CODEWITHSUNDEEP
javascriptperformancerecursion
beni0888
beni0888

Reputation: 1244

Javascript recursive function performance degradation

I've been made the following question during a hiring process skills test:

var x = function(z) {
    console.log(z);    
    if (z > 0) {
        x(z-1);
    }
};

why this is progressively slower as z get higher? propose a better version, keeping it recursive.

And I want to know the answer just to learn about it. I answered that it gets slower because as z increases the number of recursive calls increases too, but I could not provide a better version. In addition, I don't know if there is any further reason why the function become slower as z get higher.

Upvotes: 9

Views: 1341

Answers (2)

jdarling
jdarling

Reputation: 2528

Since JavaScript doesn't have true tail calls (yet) what you are experiencing isn't a slowdown based on the value of z but a slowdown based on stack growth and the inability of the garbage collector (GC) to cleanup the stack of scopes that are necessary to retain this functionality.

In theory, you can change this behavior by using setImmediate and the callback pattern to solve for this. Using setImmediate allows the scope of the current execution loop to fall out of use and get collected during the next GC cycle.

So, something like:

var x = function x(z){
    console.log(z);    
    if (z > 0) {
        setImmediate(function(){
          x(z-1);
        });
    }
};

But this will not work because z is passed down into the scope for setImmediate and thus the previous scope of x can't be GC'd properly.

Instead you have to use IIFE (Immediately Invoked Function Expression) to achieve what you are looking for in combination with using setImmediate to allow the execution cycle to have time to allow for GC:

var x = function x(z){
    console.log(z);    
    if (z > 0) {
        setImmediate((function(newZ){
          return function(){
            x(newZ);
          };
        })(z-1));
    }
};

Barring any typos I think I got the above correct. Of course if your using ES6 you can shorthand this greatly as well.

The other side of this equation is the spooling effect of console.log and the buffer resizes your going to incur for doing this in a browser. In an OS terminal these costs will be minimized as backbuffer scroll is limited and the back buffer is pre-allocated and reused.

Upvotes: 2

user663031
user663031

Reputation:

The correct answer would have been, "It should not be progressively slower as z gets higher". In fact, it does not in my simple tests. My tests overflow the stack before any slowdown is visible.

I cannot imagine any alternative way to write the function while maintaining its recursive nature.

Upvotes: 11

Related Questions