如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
堆栈溢出只会发生在编程语言没有内置内存管理....否则,请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归,就不可能有这样的东西……谷歌或SQL,或任何地方一个人必须有效地排序大型数据结构(类)或数据库。
如果你想要遍历文件,递归是一种方法,我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归,特别是管道(但不要像很多人那样做一堆系统调用,如果你要把它放在那里供别人使用的话)。
高级语言,甚至clang/cpp也可以在后台实现相同的功能。
其他回答
递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。
尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。
递归和迭代取决于您想要实现的业务逻辑,尽管在大多数情况下可以互换使用。大多数开发人员选择递归,因为它更容易理解。
递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。
我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。
递归?从哪里开始呢,维基会告诉你"这是以一种自相似的方式重复项目的过程"
在我做C语言的时候,c++的递归是上帝的恩赐,就像“尾递归”。您还会发现许多排序算法使用递归。快速排序示例:http://alienryderflex.com/quicksort/
递归就像任何其他算法一样,适用于特定的问题。也许你不能马上或经常找到一个用途,但会有问题,你会很高兴它可用。
使用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次循环时,递归再次以更大的优势获胜