Javascript recursive function performance degradation

Question

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.

It takes more time because it logs to the console more often? It's really hard to imagine what they wanted to hear. Did you ask them? — Bergi, Feb 16 '16 at 16:44
No, I haven't been able to to ask them yet but I'll do it if I can. — beni0888, Feb 16 '16 at 16:46
If they indeed mean that this is exponentially slower for large numbers of `z` than for small numbers, the only real reason for that would be that functions on the top of large call stacks would somehow execute more and more slowly; that the call stack would somehow accumulate overhead. This obviously greatly depends on the Javascript implementation. Have you run any tests to confirm that this in fact does slow down? — deceze, Feb 16 '16 at 16:48
I did some manual tests in google chrome's debugger console during the tests, but I couldn't test it deeply because I had a time limit to answer the question. I my test I saw that if call the function with a really bit value for z it gets slower than with smaller values, but I can't say the exact proportion. — beni0888, Feb 16 '16 at 16:56
Are you sure you recall an exact code snippet? I imagine a question about a recursive fibonacci function that calls itself twice thus leading to actually observable growth of recursive calls. This opens up a discussion of a possible cache, an iterative version or even a version with an accumulator and a single recursion. — Wiktor Zychla, Feb 16 '16 at 17:01
Maibe they want a trampoline like is explaned into this link http://stackoverflow.com/questions/25228871/how-to-understand-trampoline-in-javascript — Roger Russel, Feb 16 '16 at 17:39
@WiktorZychla yeah, the snippet was exactly as I've written it here — beni0888, Feb 16 '16 at 17:45
I'll ask to some guy at the company if he can give me the right answer or a proper reason for the "supposed" performance degradation, just to make things clear. I'll put it here when I have it — beni0888, Feb 16 '16 at 17:48

score 11 · Answer 1 · 2016-02-16T17:01:33.937

11

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.

edited Feb 16 '16 at 17:01

answered Feb 16 '16 at 16:50

I was brushing up on [Duff's Device](http://eemyop.blogspot.co.uk/2013/05/duffs-device-in-javascript-optimization.html) to see if that could be a sensible answer, but trying to do that recursively throws a `Too much recursion` error with `x(1000)`. I think this may have been what the question was hinting at, but I think your answer is correct. – James Long Feb 16 '16 at 16:54

score 1 · Answer 2 · answered Feb 17 '16 at 18:40

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.

Javascript recursive function performance degradation

2 Answers2