Speed up a recursive function in javascript

Question

Is there any way to speed up the execution of this recursive function and keeping it recursive?

var printDecreased = function(z) {
    console.log(z);

    if (z > 0) {
        printDecreased(z-1);
    }
};

printDecreased(50);

Since this has a single recursive call I don't think there are many ways to speed up it

Answer 1

You can increase the speed a slight bit by avoiding the if statement like so:

var printDecreased = function(z) {
    console.log(z);

    (z > 0 && printDecreased(z-1));
};

printDecreased(50);

But the increase is only very slight (about 5-10%)

How does that work?

The keyword here is branch prediction. I will not go into detail about branch prediction, since that's not what the question was about. Bottom line is, branches cost quite a lot of CPU time, which means, each if is quite expensive and if you want to improve the speed of a heavily used line then try your best to leave out all branches.

The easiest way to do that is by replacing if/else constructs that only contain one statement on each side by ternary operators and if constructs that contain only one statement in total by the && or || operators. These are generally speaking much faster than ifs or if/elses. This can be applied to almost any programming language that supports these constructs.

Examples

if (x==y) {
    callA();
} else {
    callB();
}

can be replaced with

(x==y ? callA() : callB());

and

if (x==y) {
    callA();
}

can be replaced by

(x==y && callA());

or

(x!=y || callA());

These options give the compiler better clues on how to optimize, so it can optimize the branch prediction.

Other possible optimizations The example can hardly be optimized any better than it is so far, with the given limitations. Since this is such a trivial function the function call overhead makes up quite a substantial part of the execution time. If you can replace the recursion with a loop (which is easily done in the given example) you can, generally speaking, speed up the process quite a lot as well. Removing recursions speeds up functions in most programming languages, since calling functions usually costs a lot of CPU time.

Answer 2

One possible way to speed up the function would be to add a little bit of redundancy to it. For example, using Duff's device we can attempt to boost the performance of the function:

function printDecreasedOptimized(z) {
    console.log(z);

    if (z > 0) {
        switch (z % 8) {
        case 0: console.log(--z);
        case 7: console.log(--z);
        case 6: console.log(--z);
        case 5: console.log(--z);
        case 4: console.log(--z);
        case 3: console.log(--z);
        case 2: console.log(--z);
        case 1: console.log(--z);
        }

        (z > 0 && printDecreasedDuff(z));
    }
}

function printDecreasedDuff(z) {
    console.log(--z);
    console.log(--z);
    console.log(--z);
    console.log(--z);
    console.log(--z);
    console.log(--z);
    console.log(--z);
    console.log(--z);

    (z > 0 && printDecreasedDuff(z));
}

The idea is to perform eight iterations at a time, thereby saving the cost of seven function call overheads. Surprisingly, on benchmarking this code I found that this optimization doesn't make much of a difference to performance.

I surmise that modern JavaScript engines like V8 and SpiderMonkey are smart enough to optimize such recursive functions. Therefore, you don't need to worry about performance of such functions. Indeed, premature optimization is the root of all evil.

BTW, with proper tails calls around the corner your recursive functions will only become faster.