如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
在许多情况下,由于缓存提高了性能,递归更快。例如,这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢,因为缓存改进了性能。
迭代实现
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上的算法课程上讲的。
其他回答
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.
例如,在某些语言中,存在递归多线程归并排序实现。
但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。
递归有一个缺点,使用递归编写的算法的空间复杂度为O(n)。 而迭代方法的空间复杂度为O(1)。这是使用迭代而不是递归的优点。 那我们为什么要用递归呢?
见下文。
有时使用递归编写算法更容易,而使用迭代编写相同的算法略难。在这种情况下,如果您选择遵循迭代方法,您将不得不自己处理堆栈。
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。
我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。
递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。
尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。
推荐文章
- 在SQL Server上使用varchar(MAX) vs TEXT
- 就地基数排序
- .toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
- 是什么导致JNI调用变慢?
- 检查属性是否有属性
- 如何快速清除JavaScript对象?
- 投弹算法
- 排序10个数字的最快方法?(数字为32位)
- Node.js vs .Net性能
- 如果使用if-return-return或if-else-return?
- 数组与链表
- 为什么MYSQL的高LIMIT偏移量减慢查询?
- SQL JOIN vs IN性能?
- 计算趋势主题或标签的最佳方法是什么?
- 如何找到JavaScript数组中包含的最大数字?