我知道递归有时比循环要简洁得多，我不是在问什么时候应该用递归而不是迭代，我知道已经有很多关于这个的问题了。
我问的是，递归比循环快吗?在我看来，你总是能够细化一个循环，让它比递归函数执行得更快，因为循环是不存在的，不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快，例如在一些排序函数中，在二叉树中等等。
当前回答
递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。
因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。
其他回答
递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。
因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。
一般来说，不，在任何具有两种形式的可行实现的实际使用中，递归不会比循环快。我的意思是，当然，你可以编写出花费很长时间的循环，但是有更好的方法来实现相同的循环，可以通过递归来实现相同的问题。
关于原因，你一针见血;创建和销毁堆栈帧比简单的跳转代价更大。
但是，请注意我所说的“在两种形式中都有可行的实现”。对于像许多排序算法这样的事情，往往没有一种非常可行的方法来实现它们，因为它不能有效地建立自己的堆栈版本，因为生成子“任务”是这个过程固有的一部分。因此，递归可能和试图通过循环实现算法一样快。
编辑:这个答案是假设非函数式语言，其中大多数基本数据类型是可变的。它不适用于函数式语言。
尾递归和循环一样快。许多函数式语言都实现了尾部递归。
函数式编程更多的是关于“是什么”而不是“如何”。
语言实现者会找到一种方法来优化代码在底层的工作方式，如果我们不试图让它比它需要的更优化的话。递归也可以在支持尾部调用优化的语言中进行优化。
从程序员的角度来看，更重要的是可读性和可维护性，而不是首先进行优化。再次强调，“过早优化是万恶之源”。
这里有一个例子，在Java中递归比循环运行得快。这是一个对两个数组执行冒泡排序的程序。recBubbleSort(....)方法使用递归对数组arr排序，bbSort(....)方法仅使用循环对数组narr排序。两个数组中的数据是相同的。
public class BBSort_App {
public static void main(String args[]) {
int[] arr = {231,414235,23,543,245,6,324,-32552,-4};
long time = System.nanoTime();
recBubbleSort(arr, arr.length-1, 0);
time = System.nanoTime() - time;
System.out.println("Time Elapsed: "+time+"nanos");
disp(arr);
int[] narr = {231,414235,23,543,245,6,324,-32552,-4};
time = System.nanoTime();
bbSort(narr);
time = System.nanoTime()-time;
System.out.println("Time Elapsed: "+time+"nanos");
disp(narr);
}
static void disp(int[] origin) {
System.out.print("[");
for(int b: origin)
System.out.print(b+", ");
System.out.println("\b\b \b]");
}
static void recBubbleSort(int[] origin, int i, int j) {
if(i>0)
if(j!=i) {
if(origin[i]<origin[j]) {
int temp = origin[i];
origin[i] = origin[j];
origin[j] = temp;
}
recBubbleSort(origin, i, j+1);
}
else
recBubbleSort(origin, i-1, 0);
}
static void bbSort(int[] origin) {
for(int out=origin.length-1;out>0;out--)
for(int in=0;in<out;in++)
if(origin[out]<origin[in]) {
int temp = origin[out];
origin[out] = origin[in];
origin[in] = temp;
}
}
}
即使运行该测试50次，也会得到几乎相同的结果:
对这个问题的回答是令人满意的，但没有简单的例子。有人能给出为什么这个递归更快的原因吗?
