递归是否总能提高性能？

Question

这里我有两个解决方案来判断一个srting是否是回文。第一个使用递归，第二个使用 for 循环。我有点困惑我的递归代码与没有递归的代码的执行方式。递归运行的代码是否在 O(n) 时间内？如果可以，怎么做？

//Solution using recursion
function isPalindrome(arr) {
    //Runs on first call only
    if (typeof arr === "string"){
        //remove whitespace
        if(arr.match(/\s/)) {
            arr = arr.replace(/\s/g, "");
        }
        //convert to array
        arr = arr.split("");
    }

    //base condition
    if(arr.length === 0 || arr.length === 1) {
        //console.log(true);
        return true;
    } else {
        if (arr[0] !== arr[arr.length - 1]) {
            //console.log(false);
            return false;
        } else {
            arr.shift(); //remove first element
            arr.pop(); //remove last element

            //recursive call
            isPalindrome(arr);
        }
    }
}

//Solution without using recursion
function palindrome(str) {
    var reverseString = [];
    //remove whitespace
    if(str.match(/\s/)) {
        str = str.replace(/\s/g, "");
    }
    //convert to array
    var arr = str.split("");

    for(var i = arr.length; i > 0; i--) {
        reverseString.push(arr.pop());
    }

    if (reverseString.join("") === str) {
        return true;
    } else {
        return false;
    }

}

console.log(palindrome("racecar"));
console.log(palindrome("si racecar is"));

Answer 1

正在回答您的标题问题：

不，递归不会提高性能。它很可能总是使实现变慢（与基于相同循环的对应物相比）

关于复杂度：

您的递归解决方案可能是 O(n^2)，因为 arr.shift() 操作可能是线性的。

从 V8 实现开始：array.shift 操作是线性的。参见 https://github.com/v8/v8/blob/master/src/array.js#L596 and https://github.com/v8/v8/blob/master/src/array.js#L313

替代实施：

function isPalindromeZ(s) {
    for (var i = 0, len = s.length; i < len / 2; ++i) {
        if (s[i] != s[len - i - 1]) {
            return false;
        }
    }

    return true;
}

与您的实现相比，此实现的优点在于它 O(1) 额外的内存消耗。

Answer 2

不，递归本身不会提高性能，相反。递归调用增加了一些开销，因此递归解决方案通常比迭代解决方案慢一些，如果存在一个简单的解决方案（如示例中所示）。

递归可用于简化某些自然嵌套的任务，这些任务需要迭代解决复杂的代码。这就是递归可以提高性能的情况，通过消除如此多的复杂性，它远远超过它增加的小开销。

您问题中的示例不是如何使用递归的好示例。可以用来演示递归如何工作，但不能演示递归如何用好。

递归版本没有 O(n) 复杂度，更接近于 O(n²) 复杂度。 arr.shift() 调用将移动数组中的所有项目，这意味着每次迭代都有一个运行剩余数组长度的内部循环。

此外，递归版本中存在错误；最后一行应该是：

return isPalindrome(arr);

递归是否总能提高性能？

Does recursion always improves performance?

javascript

recursion

performance

big-o

for-loop