我知道递归有时比循环要简洁得多，我不是在问什么时候应该用递归而不是迭代，我知道已经有很多关于这个的问题了。
我问的是，递归比循环快吗?在我看来，你总是能够细化一个循环，让它比递归函数执行得更快，因为循环是不存在的，不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快，例如在一些排序函数中，在二叉树中等等。
当前回答
递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。
因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。
其他回答
函数式编程更多的是关于“是什么”而不是“如何”。
语言实现者会找到一种方法来优化代码在底层的工作方式，如果我们不试图让它比它需要的更优化的话。递归也可以在支持尾部调用优化的语言中进行优化。
从程序员的角度来看，更重要的是可读性和可维护性，而不是首先进行优化。再次强调，“过早优化是万恶之源”。
从理论上讲，两者是一样的。 具有相同O()复杂度的递归和循环将以相同的理论速度工作，但当然，实际速度取决于语言、编译器和处理器。 数幂例可用O(ln(n))迭代编码:
int power(int t, int k) {
int res = 1;
while (k) {
if (k & 1) res *= t;
t *= t;
k >>= 1;
}
return res;
}
递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。
因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。
这取决于使用的语言。你写了'language-agnostic'，所以我会举一些例子。
在Java、C和Python中，与迭代相比，递归是相当昂贵的(通常)，因为它需要分配一个新的堆栈框架。在一些C编译器中，可以使用编译器标志来消除这种开销，它将某些类型的递归(实际上是某些类型的尾部调用)转换为跳转而不是函数调用。
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实现中，递归通常比循环快。
简而言之，答案取决于代码和实现。你喜欢什么风格就用什么风格。如果使用函数式语言，递归可能更快。如果使用命令式语言，迭代可能更快。在某些环境中，这两种方法将生成相同的程序集(将其放入管道中并吸食)。
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.
列表推导式是另一种选择，但它们通常只是用于迭代、递归或更高阶函数的语法糖。
考虑每个迭代和递归都必须做什么。
迭代:跳转到循环的开始 递归:跳转到被调用函数的开头
你看，这里没有多少分歧的余地。
(我假设递归是尾部调用，编译器知道这种优化)。
