如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?


当前回答

迈克说得对。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++的铁杆用户。