javascript - 即使不存在递归函数，JavaScript 堆栈也会溢出

Question

假设我们想通过使用 lambdas 作为代表我们想要添加新数据的位置的“洞”来构建大型结构。例如，在这里我们[0,[1,[2,null]]]使用这个想法构建：

builder_0 = hole => hole;                // hole => hole;
builder_1 = hole => builder_0([0,hole]); // hole => [0, hole];
builder_2 = hole => builder_1([1,hole]); // hole => [0, [1, hole]];
builder_3 = hole => builder_2([2,hole]); // hole => [0, [1, [2, hole]]];

// prints [0,[1,[2,null]]], but will stack overflows if too many lines
console.log(JSON.stringify(builder_3(null)));

这工作正常。我们也可以循环执行：

let builder = hole => hole;
for (let i = 0; i < 1000; ++i) {
  let last_builder = builder;
  builder = hole => last_builder([i, hole]);
};
console.log(builder(null));

这也有效，但如果限制大于 ，此算法将堆栈溢出10000。问题是，由于last_builder([i,hole])没有在hole => ...闭包内部进行评估，它会构建大量未评估的 lambdas，这些 lambdas 将迅速消耗整个堆栈。请注意，这[0,[1,[2,null]]]只是一个无用的示例，JavaScript 将无法使用上述基于孔的技术构建任何大型结构（想想树、JSON、不可变容器等）。

尾调用优化和蹦床在这里无济于事，因为我们甚至没有递归函数开始。有没有什么巧妙的技巧可以让这种函数式习语在没有堆栈溢出的情况下工作？

标签： javascriptfunctional-programmingstack-overflow

Answer 1

当你在编译函数式代码时，你可以让自己在 JS 部分中没有“函数式”。因此，您无需递归即可创建所需的数据结构：

const builder = (count,hole) => {
   let arr = [hole];
   let i = 0;
   while (count--) arr = [count,arr]
   return arr;
}

console.log(builder(22333,null))

（请在浏览器的控制台上试一试，因为代码片段工具无法重现它）