JavaScript递归实现foldl函数遇RangeError：调用栈溢出

你遇到的RangeError: Maximum call stack size exceeded错误，核心原因是递归的终止条件永远无法触发，同时折叠函数的参数顺序也不符合左折叠的逻辑。咱们一步步拆解问题：

问题出在哪？ #

看你的代码：

var foldl = function(f, acc, array) { 
  if (array.length == 0) { return acc; } 
  else { return f(array[0], foldl(f, acc, array.slice(-1))); } 
}

1. 数组处理错误：array.slice(-1)的作用是返回数组的最后一个元素组成的新数组（比如对[1,2,3]调用后会得到[3]），而不是去掉第一个元素后的剩余数组。这意味着每次递归调用时，传入的数组永远是[3]，永远满足不了array.length == 0的终止条件，递归会无限循环直到栈被撑爆。
2. 参数顺序错误：左折叠（foldl）的逻辑是用当前累加器和数组的第一个元素计算新的累加器，再递归处理剩余数组。但你这里把array[0]作为f的第一个参数，把递归结果作为第二个参数，这其实更接近右折叠（foldr）的参数顺序，完全不符合左折叠的预期。

修正后的递归foldl实现 #

下面是正确的代码：

var foldl = function(f, acc, array) {
  if (array.length === 0) {
    return acc;
  } else {
    // 1. 用slice(1)获取去掉第一个元素后的剩余数组
    // 2. 先计算新的累加器：f(acc, array[0])，再传入下一次递归
    return foldl(f, f(acc, array[0]), array.slice(1));
  }
}

验证一下 #

运行你的测试用例：

console.log(foldl(function(x, y) { return x + y }, 0, [1, 2, 3]))

会得到正确结果6，计算过程是((0 + 1) + 2) + 3 = 6，完全符合左折叠的计算逻辑。

额外说明 #

如果需要处理非常大的数组，递归版的foldl可能还是会遇到栈溢出问题（因为JavaScript的调用栈深度有限），这种情况下可以考虑用迭代实现或者利用尾递归优化（不过不是所有JavaScript引擎都支持尾递归优化）。但对于常规规模的数组，上面的递归实现已经足够好用了。

内容的提问来源于stack exchange，提问作者Lucy