为什么在JavaScript中递归如此缓慢？

Question

我刚在jsperf上运行了这个基准测试：https://jsperf.com/mapping1 我试图看看使用递归的map函数是否能击败Array.prototype的map函数。结果我的代码输了。请问有人可以解释为什么吗？

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...

- dopatraman

---

.concat()创建一个新数组。 - robertklep

那 Array.prototype.map() 也是这样的吧？ - dopatraman

与[<elem>]相同。你可能也在对数组进行头尾切片，而map则会原地对数组进行操作，并将聚合的输出放入一个新的单一数组中。 - Patrick M

@dopatraman：是的，但 Array::map 只创建一个新数组。而你的函数在每个递归步骤中都会创建 3 个新数组。 - Bergi

尝试使用记忆化运行您的递归。 - Inacio Schweller

Answer 1

这里是 fasterMap 的递归实现，但没有使用 concat，比 map 快 20 倍，只比原生的 Array.map 慢 1.5 倍：

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)
        }
    })
})

这是在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 

因此，concat使您的map函数变慢。

- alpav