performance - 递归比循环更快吗？

Question

我知道递归有时比循环干净得多，而且我不会问什么时候应该使用递归而不是迭代，我知道已经有很多关于这一点的问题了。

我要问的是，递归曾经比循环更快吗？在我看来，您总是能够改进循环并使其比递归函数执行得更快，因为循环不存在，不断地设置新的堆栈帧。

我专门寻找在递归是处理数据的正确方法的应用程序中递归是否更快，例如在某些排序函数、二叉树等中。

Answer 1

这取决于所使用的语言。您写了“与语言无关”，所以我将举一些例子。

在 Java、C 和 Python 中，与迭代(通常)相比，递归的开销相当大，因为它需要分配新的堆栈帧。在某些 C 编译器中，可以使用编译器标志来消除这种开销，从而将某些类型的递归(实际上是某些类型的尾调用)转换为跳转而不是函数调用。

在函数式编程语言实现中，有时迭代可能非常昂贵，而递归可能非常便宜。在许多情况下，递归被转换为简单的跳转，但是更改循环变量(可变的)有时需要一些相对繁重的操作，特别是在支持多线程执行的实现上。在其中一些环境中，由于更改器(mutator)和垃圾收集器之间的交互(如果两者可能同时运行)，变异的成本很高。

我知道在某些Scheme实现中，递归通常比循环更快。

简而言之，答案取决于代码和实现。使用您喜欢的任何风格。如果您使用函数式语言，递归可能会更快。如果您使用命令式语言，迭代可能会更快。在某些环境中，这两种方法都会生成相同的程序集(将其放入管道中并对其进行熏烟)。

附录:在某些环境中，最好的替代方案既不是递归也不是迭代，而是高阶函数。其中包括“map”、“filter”和“reduce”(也称为“fold”)。这些不仅是首选样式，不仅通常更干净，而且在某些环境中，这些函数是第一个(或唯一)从自动并行化中获得提升的函数 - 因此它们可以比迭代或递归更快。 Data Parallel Haskell 就是此类环境的一个示例。

列表推导式是另一种选择，但它们通常只是迭代、递归或高阶函数的语法糖。