递归比循环更快吗？

Question

递归比循环更快吗？

我知道递归有时比循环更清晰，而且我不会询问何时应该使用递归迭代，我知道有很多问题已经存在。

我要问的是，递归是否比循环更快？对我来说，似乎总是能够改进循环并让它比递归函数更快地执行，因为循环不会不断地设置新的堆栈帧。

我特别关注在递归是处理数据的正确方法的应用程序中递归是否更快，例如在一些排序函数，二叉树等中。

Answer 1

这取决于使用的语言。你写了'语言不可知'，所以我举一些例子。在Java，C和Python中，与迭代（通常）相比，递归相当昂贵，因为它需要分配新的堆栈帧。在某些C编译器中，可以使用编译器标志来消除此开销，这会将某些类型的递归（实际上是某些类型的尾调用）转换为跳转而不是函数调用。在函数式编程语言实现中，有时，迭代可能非常昂贵，并且递归可能非常便宜。在许多情况下，递归转换为简单的跳转，但是更改循环变量（这是可变的）有时需要一些相对繁重的操作，尤其是在支持多个执行线程的实现上。由于mutator和垃圾收集器之间的交互，如果两者可能同时运行，在某些环境中突变是昂贵的。我知道在一些Scheme实现中，递归通常比循环更快。简而言之，答案取决于代码和实现。使用您喜欢的任何风格。如果您使用的是函数式语言，则递归可能会更快。如果您使用命令式语言，迭代可能会更快。在某些环境中，这两种方法都会导致生成相同的程序集（将其放入管道并对其进行抽吸）。附录：在某些环境中，最好的选择既不是递归也不是迭代，而是高阶函数。这些包括“map”，“filter”和“reduce”（也称为“fold”）。这些不仅是首选样式，不仅通常更清晰，而且在某些环境中，这些函数是第一个（或唯一）从自动并行化中获得提升的功能 - 因此它们可以比迭代或递归快得多。Data Parallel Haskell就是这种环境的一个例子。列表推导是另一种选择，但这些通常只是迭代，递归或更高阶函数的语法糖。

Answer 2

如果替代方法是显式管理堆栈，递归可能会更快，就像您提到的排序或二叉树算法一样。我有一个案例，用Java重写递归算法使它变慢。因此，正确的方法是首先以最自然的方式编写它，只有在分析显示它是关键的时候进行优化，然后测量所谓的改进。