如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
迈克说得对。Java编译器或JVM没有优化尾部递归。你总是会得到这样的堆栈溢出:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
其他回答
使用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次循环时,递归再次以更大的优势获胜
迈克说得对。Java编译器或JVM没有优化尾部递归。你总是会得到这样的堆栈溢出:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
如果你只是在一个列表上迭代,那么当然,迭代出去。
其他几个答案提到了(深度优先)树遍历。这真的是一个很好的例子,因为这是对一个非常普通的数据结构所做的非常普通的事情。对于这个问题,递归是非常直观的。
点击这里查看“查找”方法: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的,在这样的系统中,甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统,具有递归函数。但是如果你想正确地定义一个迭代,你需要更多的原语来开始。
至于代码——不,递归代码实际上比纯迭代代码更容易理解和维护,因为大多数数据结构都是递归的。当然,为了正确使用它,至少需要一种支持高阶函数和闭包的语言,以简洁的方式获得所有标准的组合子和迭代器。当然,在c++中,复杂的递归解决方案可能看起来有点丑,除非你是fc++的铁杆用户。
推荐文章
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 在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性能?
- 计算趋势主题或标签的最佳方法是什么?