我知道递归有时比循环要简洁得多，我不是在问什么时候应该用递归而不是迭代，我知道已经有很多关于这个的问题了。
我问的是，递归比循环快吗?在我看来，你总是能够细化一个循环，让它比递归函数执行得更快，因为循环是不存在的，不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快，例如在一些排序函数中，在二叉树中等等。
当前回答
从理论上讲，两者是一样的。 具有相同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重写递归算法会让它变慢。
因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。
考虑每个迭代和递归都必须做什么。
迭代:跳转到循环的开始 递归:跳转到被调用函数的开头
你看，这里没有多少分歧的余地。
(我假设递归是尾部调用，编译器知道这种优化)。
从理论上讲，两者是一样的。 具有相同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中递归比循环运行得快。这是一个对两个数组执行冒泡排序的程序。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次，也会得到几乎相同的结果:
对这个问题的回答是令人满意的，但没有简单的例子。有人能给出为什么这个递归更快的原因吗?
