递归是否总是提高性能

Does recursion always improves performance?

本文关键字：高性能 是否 递归      更新时间：2023-09-26

在这里，我有两个解决方案来查找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"));

回答您的标题问题：

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

关于复杂性：

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

从 V8 实现开始：array.shift操作是线性的。请参阅 https://github.com/v8/v8/blob/master/src/array.js#L596 和 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)。

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

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

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

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

此外，递归版本中还有一个错误;最后一行应该是：

return isPalindrome(arr);
相关文章：