如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
其他回答
递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。
尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。
通常情况下,人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外,在一些语言中,如Python(更准确地说,是在某些语言的某些实现中……),对于递归指定的任务,您可能很容易遇到堆栈限制,例如在树状数据结构中查找最大值。在这些情况下,你应该坚持使用循环。
编写好的递归函数可以在一定程度上降低性能损失,前提是你有一个优化尾部递归的编译器,等等(还要再次检查,确保函数真的是尾部递归——这是许多人都会犯的错误之一)。
除了“边缘”情况(高性能计算、非常大的递归深度等)之外,最好采用最清楚地表达您的意图、设计良好且可维护的方法。仅在确定需求后进行优化。
使用Chrome 45.0.2454.85 m,递归似乎要快得多。
代码如下:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do('recursion', function() {
recurFn(function() {
console.log('a recur run.');
}, testsToRun);
});
curTest.do('loop', function() {
loopFn(function() {
console.log('a loop run.');
}, testsToRun);
});
})(window);
结果
//使用标准for循环运行100次
循环运行100x。 完成时间:7.683ms
//使用带有尾递归的函数递归方法运行100次
100x递归运行。 完成时间:4.841毫秒
在下面的截图中,当每次测试运行300次循环时,递归再次以更大的优势获胜
使用递归,每次“迭代”都会产生函数调用的成本,而使用循环,你通常只需要支付递增/递减的代价。因此,如果循环的代码并不比递归解决方案的代码复杂多少,循环通常会优于递归。
在许多情况下,由于缓存提高了性能,递归更快。例如,这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢,因为缓存改进了性能。
迭代实现
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上的算法课程上讲的。