c++ - 递归回文检验

Question

我有一个原型限制，bool pal(char str[], int length)我需要测试用户输入的字符串是否是回文。我的代码是：

bool pal(char str[], int length)
{
    if(*str == str[length - 1])
    {
        pal(str+1, length-1);
    }
    else
    {
        return false
    }
    return true;
}

但它似乎只是在测试第一个字符是否与最后一个字符相同。我认为这是因为我的数组（起点）没有增加，但我不知道为什么。

Answer 1

这是您的代码的工作版本。

bool pal(const char* str, int length)
{
   if(length <2) return true; // base case - 1 or 0 length string is a palindrome.
   if((*str) == str[length - 1])
   {
     return pal(str+1, length-2); // -2 because 1 from front and 1 from back. 
   }
   else
   {
     return false;
   }
    //no return here because the recursive call is returned.
}

Answer 2

我想这可能是由于对陈述的一些根深蒂固的厌恶if，但如果由我决定，我想我会编写如下代码：

bool pal(char *str, size_t len) { 
    return len <2 || (str[0] == str[len-1] && pal(str+1, len-2));
}

Answer 3

您检查第一个和最后一个字符，因此您应该将长度减少 2，而不是减少 1。此外，您应该返回内部 pal 调用的值，而不是丢弃它。

if(*str == str[length - 1])
{
    return pal(str + 1, length - 2);
}

对长度 >=2 且 str 不为空的附加测试也将是有序的。

Answer 4

您的主要问题是您对递归调用的结果不做任何事情：

 if(*str == str[length - 1])
    {
        pal(str+1, length-1);
    }

应该是：

 if(*str == str[length - 1])
    {
        return pal(str+1, length-1);
    }

您还需要检查诸如零长度字符串或只有单个字符的字符串之类的东西。