Why is recursion faster than a flat for loop for a summation function on JavaScript?

Question

I'm working in a language that translates to JavaScript. In order to avoid some stack overflows, I'm applying tail call optimization by converting certain functions to for loops. What is surprising is that the conversion is not faster than the recursive version.

http://jsperf.com/sldjf-lajf-lkajf-lkfadsj-f/5

Recursive version:

(function recur(a0,s0){
    return a0==0 ? s0 : recur(a0-1, a0+s0)
})(10000,0)

After tail call optimization:

ret3 = void 0;
a1   = 10000;
s2   = 0;
(function(){
    while (!ret3) {
        a1 == 0 
            ? ret3     = s2
            : (a1_tmp$ = a1 - 1 ,
               s2_tmp$ = a1 + s2,
               a1      = a1_tmp$,
               s2      = s2_tmp$);
     }
})();
ret3;

After some cleanup using Google Closure Compiler:

ret3 = 0;
a1   = 1E4;
for(s2 = 0; ret3 == 0;)
    0 == a1 
        ? ret3     = s2 
        : (a1_tmp$ = a1 - 1 ,
           s2_tmp$ = a1 + s2,
           a1      = a1_tmp$,
           s2      = s2_tmp$);
c=ret3;

The recursive version is faster than the "optimized" ones! How can this be possible, if the recursive version has to handle thousands of context changes?

Answer 1

There's more to optimising than tail-call optimisation.

For instance, I notice you're using two temporary variables, when all you need is:

s2 += a1;
a1--;

This alone practically reduces the number of operations by a third, resulting in a performance increase of 50%

In the long run, it's important to optimise what operations are being performed before trying to optimise the operations themselves.

EDIT: Here's an updated jsperf

Answer 2

as Kolink say what your piece of code do is simply adding n to the total, reduce n by 1, and loop until n not reach 0

so just do that :

n = 10000, o = 0; while(n) o += n--;

it's more faster and lisible than the recursive version, and off course output the same result