性能: Javascript中的递归和迭代

Question

我最近读过一些关于Javascript功能方面的文章(例如http://dailyjs.com/2012/09/14/functional-programming/)，以及方案和Javascript之间的关系(后者受第一种功能语言的影响，而O方面则是从基于原型的自我语言中继承而来)。

然而，我的问题更具体:我想知道是否有关于Javascript中递归和迭代性能的度量标准。

我知道，在某些语言(通过设计迭代执行得更好)中，差异很小，因为解释器/编译器将递归转换为迭代，但是我猜想Javascript可能不是这种情况，因为它至少部分是一种函数式语言。

Answer 1

JavaScript 不执行尾递归优化。，因此如果递归太深，则可能会出现调用堆栈溢出。迭代没有这样的问题。如果您认为您要递归太多，而您确实需要递归(例如，做洪水填充)，那么用您自己的堆栈替换递归。

递归性能可能比迭代性能差，因为函数调用和返回需要状态保存和恢复，而迭代只是跳到函数中的另一个点。

Answer 2

根据任择议定书的请求，我会加入(不让自己出丑，希望是:P)

我认为我们都同意递归只是一种更优雅的编码方式。如果做得好，它可以生成更易于维护的代码，这与减少0.0001ms一样重要(如果不是更重要的话)。

关于JS不执行尾调用优化的论点:这不再是完全正确的了，采用ECMA5 5 5‘S严格模式启用了TCO。这是一段时间前我不太高兴的事情，但至少我现在知道为什么arguments.callee在严格模式下抛出错误。我知道上面链接到一个bug报告，但是这个bug被设置为WONTFIX。此外，标准TCO即将到来: ECMA6 (2013年12月)。

本能地，并且坚持JS的功能特性，我会说递归是99.99%情况下更有效的编码风格。然而，弗洛里安·马加因说，瓶颈很可能在其他地方找到，这是有道理的。如果您正在操作DOM，您可能最好集中精力编写尽可能可维护的代码。DOM就是它的特点:慢。

我认为几乎不可能给出一个明确的答案，哪一个是更快的选择。最近，我看到的很多jspref显示，Chrome的V8引擎在某些任务上运行得非常快，在FF的SpiderMonkey上运行速度慢了4倍，反之亦然。现代JS引擎有各种各样的技巧来优化您的代码。我不是专家，但我确实觉得V8对于闭包(和递归)是高度优化的，而MS的JScript引擎则不是。当涉及DOM时，SpiderMonkey通常表现得更好..。

简而言之:我要说的是，哪种技术会更有表现力，就像在JS中一样，几乎无法预测。

Answer 3

如果没有严格的模式，迭代性能通常比递归略快(除了让JIT做更多的工作外)。尾递归优化本质上消除了任何明显的差异，因为它将整个调用序列转换为跳转。

示例：杰斯普夫

当涉及到递归和迭代之间的选择时，我建议更多地考虑代码的清晰度和简单性。