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


当前回答

使用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上的算法课程上讲的。

这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。

例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%

同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)

在很多情况下,它提供了比迭代方法更优雅的解决方案,常见的例子是遍历二叉树,所以它不一定更难维护。一般来说,迭代版本通常更快一些(在优化过程中可能会取代递归版本),但递归版本更容易理解和正确实现。

使用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中,你应该使用循环。函数式语言优化递归。