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


当前回答

递归和迭代取决于您想要实现的业务逻辑,尽管在大多数情况下可以互换使用。大多数开发人员选择递归,因为它更容易理解。

其他回答

这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。

递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。

尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。

据我所知,Perl没有优化尾递归调用,但是您可以伪造它。

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

第一次调用时,它将在堆栈上分配空间。然后它将改变它的参数,并重新启动子例程,而不向堆栈添加任何东西。因此,它会假装从未调用过自己,将其转变为一个迭代过程。

注意,没有“my @_;”或“local @_;”,如果你这样做,它将不再工作。

我相信java中的尾递归目前还没有优化。关于LtU和相关链接的详细讨论贯穿始终。它可能是即将到来的版本7中的一个功能,但显然,当与堆栈检查结合使用时,它会出现一些困难,因为某些帧会丢失。自Java 2以来,堆栈检查一直用于实现他们的细粒度安全模型。

http://lambda-the-ultimate.org/node/1333

使用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次循环时,递归再次以更大的优势获胜