如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。
例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%
同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)
其他回答
在许多情况下,由于缓存提高了性能,递归更快。例如,这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢,因为缓存改进了性能。
迭代实现
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
递归实现
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS -这是Kevin Wayne教授(普林斯顿大学)在Coursera上的算法课程上讲的。
堆栈溢出只会发生在编程语言没有内置内存管理....否则,请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归,就不可能有这样的东西……谷歌或SQL,或任何地方一个人必须有效地排序大型数据结构(类)或数据库。
如果你想要遍历文件,递归是一种方法,我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归,特别是管道(但不要像很多人那样做一堆系统调用,如果你要把它放在那里供别人使用的话)。
高级语言,甚至clang/cpp也可以在后台实现相同的功能。
迈克说得对。Java编译器或JVM没有优化尾部递归。你总是会得到这样的堆栈溢出:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them, then a recursive approach could yield a huge performance boost when combined with multithreading. If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system.
例如,在某些语言中,存在递归多线程归并排序实现。
但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。
如果你只是在一个列表上迭代,那么当然,迭代出去。
其他几个答案提到了(深度优先)树遍历。这真的是一个很好的例子,因为这是对一个非常普通的数据结构所做的非常普通的事情。对于这个问题,递归是非常直观的。
点击这里查看“查找”方法: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html