用于检查字符串是否为回文的递归布尔函数

Question

Write a recursive boolean function that returns 1 if a string is a palindrome and 0 if not.

bool ispalindrome(char str[])

注意：函数必须是递归的（不是递归函数的包装器），它必须使用给定的（上面的）签名并且不允许全局或静态变量，另外，我们不能 'destroy' 给定的字符串。

我的尝试：

bool ispalindrome(char str[]){
    bool res;
    if (*str == 0 || *(str + 1) == 0)
        return 1;
    else{
        res = ispalindrome(str + 1);

现在我卡住了，我想制作一个使用动态数组的辅助函数，该函数将删除原始字符串中的第一个和最后一个元素，并在递归调用中使用它，但我认为这不是预期的解决方案。

编辑：我取得了一些进展，但它不起作用：

bool ispalindrome(char str[]){
    bool res;
    int l = strlen(str);
    char t;
    if (*str == 0 || *(str + 1) == 0)
        return 1;
    else{
        t = str[l-1];
        str[l-1] = 0;
        res = ispalindrome(str + 1);
        if (res == 0)
            return 0;

        if (str[0] == str[l - 2])
            res =1;
        else 
            res=0;
        str[l] = t;
        return res;
    }
}

Answer 1

psuedocode（意思是，在C中没有叫string的东西，我也没有尝试编译它，我想象中的类似于真实库调用的库调用可以在订单错误等):

bool isPalendrome(string s)
{
    if (s[0] == s[strlen(s)-1]) // if the value of the first is the same as the last
    {
        if ((&s[strlen(s)-1] - &s[0]) < 3)// if the address of the end and the address of the start are 1, or 2, we have a palindrome of 1 or 2 chars..
        {
            return true;
        }
        s2 = alloca(strlen(s) - 1);// or VLA , -1 because -2 char, +1 for null
        s2[strlen(s) - 2] = '[=10=]';
        strncpy(s+1,s2,strlen(s)-2);
        return isPalendrome(s2)
    }
    return false;
}

Answer 2

没有编译器...

bool ispalindrome(char str[])
{
    int len = strlen(str);

    if( len <= 1)
    {
        return TRUE;
    }
    else if (str[0] != str[len - 1])
    {
        reutrn FALSE;
    }
    else
    {
        char *str2 = malloc(len - 1);
        strncpy(str2, str + 1, len - 2);
        str2[len - 2] = NULL;
        BOOL result = ispalindrome(str2); 
        free(str2);
        return result;
    }
}

Answer 3

因此，您当前的代码几乎可以正常工作。我看到的唯一问题是，在一种情况下，您 return 在还原字符串中的更改之前。另外，您的索引中有一个错误。

我们还要注意一些风格上的修正：

*(str + 1)确实应该是str[1]。它们是等价的，但后者是预期的。
因为您已经计算了 l = strlen(str)，您可以将其用于您的第一个条件，因为它的可读性更高。
您也可以使用更长的变量名。它们并没有更贵。
就我个人而言，如果将空字符写入字符串，我喜欢使用空字符而不是 0。即'[=16=]'。但这就是我。

代码：

bool ispalindrome(char str[]){
    int l = strlen(str);

    // Recusive Base Case
    if (l == 0 || l == 1)
        return true;

    // Save the last character of the string
    char t = str[l-1];
    str[l-1] = '[=10=]';

    // Recursive call on the substring
    bool res = ispalindrome(str + 1);

    // Now, this is where you messed up. Before we return,
    // we need to fix the string!
    str[l-1] = t;

    // If the recursive call thinks that it's not a palindrome,
    // then we won't disagree.
    if (res == false)
        return res;

    // Check the (current) first position of the string against the last
    // You had an off by one error here.
    return (str[0] == str[l - 1]);
}

我们可以对代码的运行时间做一点改进吗？

关于您的代码工作方式的一个烦人属性是我们总是会遇到 strlen(str) / 2 递归调用。在像 "abracadabra" 这样的示例中，我们能否使代码运行更快，其中字符串的第二个字母导致回文测试失败。

加快速度的一种方法是在递归调用之前进行测试(str[0] == str[l - 1]) 。我们可以很容易地实现它，它可能看起来像这样：

bool ispalindrome(char str[]){ int length = strlen(str); // Recursive Base Case if (length == 0 || length == 1) return true; // Check our case. // Note that this is occuring __before__ the recursive call if (str[0] != str[length - 1]) return false; // Save the last character of the string char t = str[length - 1]; str[length - 1] = '[=11=]'; // Recursive call on the substring bool res = ispalindrome(str + 1); // We need to fix the string str[length - 1] = t; return res; }

综上所述...

这个问题我在 Whosebug 上看过几次，我一直很好奇老师在找什么。这个问题的经典版本是通过将字符串长度作为附加参数传递来解决的。通过这样做，我们节省了吨的工作量。

到目前为止发布的每个解决方案（包括我的）都会在每次递归调用时调用 strlen()。这意味着所有这些解决方案至少是 O(n^2)。如果我们可以将长度传递给递归调用，我们可以轻松解决O(n)中的问题。这将大大减少工作量。

此外，您还可以用尾递归方式编写代码。这可以让编译器生成更适合处理器执行的代码。（基本上，它将代码转换成 for 循环的样子）。这非常有用，因为这样您就不必担心运行在非常大的字符串上 space 出栈。

但是，由于您的讲师设置的限制，我们不能做任何这些事情。这有点蹩脚。

用于检查字符串是否为回文的递归布尔函数

Recursive boolean function to check if a string is a palindrome

c

recursion

我们可以对代码的运行时间做一点改进吗？

综上所述...