Why is recursion in javascript so slow?

Question

I just ran this benchmark on jsperf: https://jsperf.com/mapping1

I was trying to see if a map that used recursion could beat the Array.prototype map function. Mine lost. Horribly. Can someone explain why?

map = function(f, xs) {
    if (xs.length === 0) {return []}
    return [f(head(xs))].concat(map(f, tail(xs)))
}

// head() and tail() do exactly what you would expect. I wish there was a way to programmatically fork lists in js...

Answer 1

Here is implementation of fasterMap recursively, but without concat, it is 20x faster than map and only 1.5x slower than native Array.map:

var Cx = function(){
    this.map = function (f, xs) {
        if (xs.length === 0) {return []}
        return [f(head(xs))].concat(arguments.callee(f, tail(xs)))
    }

    this.fasterMap = function(f, xs, i) {
        i = i || 0;
        if (xs.length === 0 || i > xs.length - 1) {return []}
        xs[i] = f(xs[i])
        arguments.callee(f, xs, i + 1)
        return xs
    }

    this.arrMap = function (f, xs) {
        return xs.map(f)
    }
}

function head(arr){return arr[0]}
function tail(arr){return arr.slice(1)}

function add1(x){return x + 1}

function rep(n,f){
    for(var i = 0; i < n; i++)
        f(i)
}

var cx = new Cx()

;[9,99,999].forEach(function(n){
    var test = []
    rep(n,function(i){test.push(i + 1)})

    ;['map','fasterMap','arrMap'].forEach(function(mapType){
        var mapFn = function(){return cx[mapType](add1,test)}
        if(n < 10)
            console.log('    ' + mapType,mapFn())
        else{
            console.time('    ' + mapType + ' ' + n)
            rep(1000,mapFn)
            console.timeEnd('    ' + mapType + ' ' + n)
        }
    })
})

Here are test results on Cloud9 IDE:

map [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                                                                                                                                                                                    
fasterMap [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]                                                                                                                                                                                                              
arrMap [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ]                                                                                                                                                                                                                

map 99: 45ms                                                                                                                                                                                                                                          
fasterMap 99: 8ms                                                                                                                                                                                                                                     
arrMap 99: 7ms                                                                                                                                                                                                                                        

map 999: 2227ms                                                                                                                                                                                                                                       
fasterMap 999: 102ms                                                                                                                                                                                                                                  
arrMap 999: 85ms 

So the answer is concat makes your map function slow.