递归比循环更快吗？ [英] Is recursion ever faster than looping?
问题描述
我知道递归有时比循环更清晰，而且我不会询问何时应该使用递归而不是迭代，我知道有很多问题已经存在。
我要问的是，递归永远比循环更快？对我来说，似乎总是能够优化循环并让它比递归函数更快地执行，因为循环不会不断设置新的堆栈帧。
我特别关注在递归是处理数据的正确方法的应用程序中递归是否更快，例如在一些排序函数，二叉树等中。
这取决于所使用的语言。你写了'语言不可知'，所以我给出一些例子。
在Java，C和Python中，与迭代相比，递归相当昂贵（一般情况下）因为它需要分配一个新的堆栈帧。在一些C编译器中，可以使用编译器标志来消除这种开销，这会将某些类型的递归（实际上是某些类型的尾调用）转换为跳转而不是函数调用。
在函数式编程语言实现中，有时，迭代可能非常昂贵，并且递归可能非常便宜。在许多情况下，递归转换为简单的跳转，但更改循环变量（可变）有时需要一些相对繁重的操作，尤其是在支持多个执行线程的实现上。由于mutator和垃圾收集器之间的交互，如果两者可能同时运行，则突变在某些环境中是昂贵的。
我知道在某些环境中方案实现，递归通常比循环更快。
简而言之，答案取决于代码和实现。使用您喜欢的任何风格。如果您使用的是函数式语言，则递归可能更快。如果您使用命令式语言，则迭代可能更快。在某些环境中，这两种方法都会导致生成相同的装配（将其放入管道中并吸烟）。
附录：在在某些环境中，最好的选择既不是递归也不是迭代，而是高阶函数。这些包括map，filter和reduce（也称为fold）。这些不仅是首选的样式，不仅通常更清晰，而且在某些环境中，这些函数是第一个（或唯一）从自动并行化中获得提升的功能 - 因此它们可以比迭代或递归快得多。 Data Parallel Haskell是这种环境的一个例子。
列表推导是另一种选择，但这些通常只是迭代，递归或更高阶函数的语法糖。 / p>
I know that recursion is sometimes a lot cleaner than looping, and I'm not asking anything about when I should use recursion over iteration, I know there are lots of questions about that already.
What I'm asking is, is recursion ever faster than a loop? To me it seems like, you would always be able to refine a loop and get it to perform more quickly than a recursive function because the loop is absent constantly setting up new stack frames.
I'm specifically looking for whether recursion is faster in applications where recursion is the right way to handle the data, such as in some sorting functions, in binary trees, etc.
This depends on the language being used. You wrote 'language-agnostic', so I'll give some examples.
In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.
In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.
I know that in some Scheme implementations, recursion will generally be faster than looping.
In short, the answer depends on the code and the implementation. Use whatever style you prefer. If you're using a functional language, recursion might be faster. If you're using an imperative language, iteration is probably faster. In some environments, both methods will result in the same assembly being generated (put that in your pipe and smoke it).
Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include "map", "filter", and "reduce" (which is also called "fold"). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.
List comprehensions are another alternative, but these are usually just syntactic sugar for iteration, recursion, or higher order functions.
这篇关于递归比循环更快吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
