递归比循环快吗? [英] Is recursion ever faster than looping?

问题描述

我知道递归有时比循环干净得多，而且我并没有问什么时候应该使用递归而不是迭代，我知道已经有很多问题了.

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.

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

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.

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

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).

附录:在某些环境中，最好的选择既不是递归也不是迭代，而是高阶函数.这些包括map"、filter"和reduce"(也称为fold").这些不仅是首选样式，而且它们通常更简洁，而且在某些环境中，这些函数是第一个(或唯一一个)从自动并行化中获得提升的函数——因此它们可以比迭代或递归快得多.Data Parallel Haskell 就是这种环境的一个例子.

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屋！