JavaScript 递归函数性能下降

Question

在招聘过程中的技能测试中，我被问到了以下问题：

var x = function(z) {
    console.log(z);    
    if (z > 0) {
        x(z-1);
    }
};

为什么随着z的增加，这个算法会越来越慢？提出一种更好的版本，保持递归。我想知道答案只是为了学习。我回答说随着z的增加，递归调用次数也会增加，所以它变得越来越慢，但我无法提供更好的版本。此外，我不知道函数在z增加时为什么会变得更慢。

- beni0888

---

因为它更频繁地记录控制台信息，所以需要更多的时间？真的很难想象他们想听什么。你有问过他们吗？ - Bergi

不，我还没有机会问他们，但如果有机会的话我会去问的。 - beni0888

如果他们确实意味着对于大量的z，这比小量的z指数级地慢，那么唯一真正的原因就是在大量调用堆栈顶部的函数会以某种方式变得越来越慢；即调用堆栈会积累开销。这显然在很大程度上取决于Javascript的实现。您是否运行过任何测试来确认这确实会减速？ - deceze

你确定你记得一个精确的代码片段吗？我想到了一个关于递归斐波那契函数的问题，它调用自身两次，从而导致递归调用的实际增长。这引发了对可能的缓存、迭代版本甚至是带有累加器和单个递归的版本的讨论。 - Wiktor Zychla

@WiktorZychla 是的，代码片段就是我在这里写的那样。 - beni0888

Answer 1

正确的答案应该是：“随着z的增加，它不应该变得越来越慢。”事实上，在我的简单测试中并没有发生这种情况。在任何减速可见之前，我的测试会溢出堆栈。

我无法想象在保持其递归性质的同时编写此函数的其他替代方式。

- user663031

---

我在温习Duff's Device以查看它是否可以作为一个明智的解答，但是尝试递归执行这个设备时会出现Too much recursion错误，并且 x(1000)也会发生这样的错误。我认为这可能是问题所提示的，但我认为你的答案是正确的。 - James Long

Answer 2

由于JavaScript目前还没有真正的尾调用优化，你所经历的不是基于z值的减速，而是基于堆栈增长和垃圾回收器（GC）无法清理必要保留此功能的作用域堆栈而导致的减速。

理论上，您可以通过使用setImmediate和回调模式来解决这个问题并改变这种行为。使用setImmediate允许当前执行循环的作用域在下一个GC周期期间失去使用并被收集。

因此，类似以下代码：

var x = function x(z){
    console.log(z);    
    if (z > 0) {
        setImmediate(function(){
          x(z-1);
        });
    }
};

但是这种方法行不通，因为z被传递到setImmediate的作用域中，因此x的先前作用域无法得到适当的垃圾回收。相反，您必须使用IIFE（立即调用函数表达式）与使用setImmediate相结合，以实现您所需求的功能，并允许执行周期有时间进行垃圾回收。

var x = function x(z){
    console.log(z);    
    if (z > 0) {
        setImmediate((function(newZ){
          return function(){
            x(newZ);
          };
        })(z-1));
    }
};

除非有拼写错误，否则我认为我已经理解了上面的内容。当然，如果您使用的是ES6，您也可以大大简化此过程。这个方程式的另一方面是控制台日志的缓冲效应和在浏览器中执行此操作时将遇到的缓冲区大小调整。在操作系统终端中，这些成本会最小化，因为后备缓冲区滚动是有限的，并且预先分配和重用了后备缓冲区。

- jdarling