回文校验的递归方法

Question

是否可以使用以下参数列表定义回文检查的递归方法？

int testPalindromeRecursive(char* str, int len) { ... }

注意：无需使用外部子函数或全局变量

我认为这是不可能的，因为你必须以某种方式记住最后一个（前面的）索引位置。

Answer 1

使用 C# 我设法得到了这个：

int testPalindromeRecursive(string str, int len)
{
    if (len <= 1)
        return 0;

    if (str[0] == str[len - 1])
    {
        str = str.Substring(1, len - 2);
        return testPalindromeRecursive(str, str.Length);
    }
    return -1;
}

ref 与 * 的工作几乎相同。 => 删除了 ref 因为它不是最佳选择，因为它不允许使用 const

Answer 2

是的，这完全有可能 - 正如几个人提到的那样。

基本案例：

如果 len <= 1，return 为真
如果 str[0] != str[len-1] return 假

否则：递归 (str+1, len -2)

Answer 3

1) 没有字符或只有一个字符的字符串是回文

2) 如果一个2个或2个以上字符的字符串首末字符相等，且除末尾字符外的子串为回文，则整个字符串为回文。

Answer 4

[EDIT2]
这是 C 语言的正确答案。虽然它被否决了 3 次，但我保留它，因为它是本页 C 语言的唯一正确答案。

[编辑]
修复了我的答案。

在 C:

#include <stdio.h>
#include <string.h>

int testPalindromeRecursive(char* str, int len)
{
    if (len <= 1)
        return 0;
    if (str[0] != str[len-1])
        return 1;
    return testPalindromeRecursive(str+1, len-2);
}

int main(int argc, char **argv)
{
    if (argc < 2)
    {
        printf("Usage: %s <string>\n", argv[0]);
        return 1;
    }
    if (!testPalindromeRecursive(argv[1], strlen(argv[1])))
        printf("Palindrom\n");
    else
        printf("Not palindrom\n");
    return 0;
}

运行 kdopen 评论中提到的案例示例（当 testPalindromeRecursive("a", 1):

时基本案例失败

./palind a  
Palindrom

更多运行 kdopen 提到的例子：

./我的\"a <-- the \ is to escape the " 不是回文

./我的\"\" 回文

Answer 5

这对我来说很好用：

#include <stdio.h>
#include <string.h>

int testPalindromeRecursive(char* str, int len)
{
    if (len <= 1)
        return 1;

    if (str[0] != str[len-1])
        return 0;

    return testPalindromeRecursive(str+1, len-2);
}

int main()
{
    int i;
    char *strs[5] = { "test", "tvt", "a", "palindrome", "racecar" };

    for (i = 0; i < 5; i++)
        printf("%s = %d\n", strs[i], testPalindromeRecursive(strs[i], strlen(strs[i])));
}

编辑：根据评论修复以检查长度==0 以及

Answer 6

至于我，那么我会像这样声明函数

int testPalindromeRecursive( const char *s, size_t n );

在这种情况下，函数将只包含一个 return 语句

int testPalindromeRecursive( const char *s, size_t n ) 
{
    return ( n < 2 ) || 
           ( s[0] == s[n-1] && testPalindromeRecursive( s + 1, n - 2 ) );   
}

尽管如此，该函数可以按以下方式编写，如下面的演示程序所示

#include <stdio.h>

int testPalindromeRecursive( char *str, int len ) 
{
    if ( len < 0 ) return 0;

    return ( len < 2 ) || 
           ( str[0] == str[len-1] && testPalindromeRecursive( str + 1, len - 2 ) );   
}

int main( void ) 
{
    char s[] = "abbcccbba"; 

    printf( "testPalindromeRecursive( \"%s\" ) is %s\n",
            s, testPalindromeRecursive( s, sizeof( s ) - 1 ) ? "true" : "false" );

    return 0;
}

程序输出为

testPalindromeRecursive( "abbcccbba" ) is true

考虑到您可能会遵守字符串函数不检查传递的字符指针是否等于 NULL 的通用约定。程序员有责任在函数调用之前对此进行检查。

Answer 7

我的解决方案能够跳过空格：

int test_palindrom_recursive(char* str, int len)
{
    if (len < 1) return 0;
    int frontIndexToPass = 0, endIndexToPass = 0;
    if (str[0] == ' ')
    {
        for (int front = 0; front < len - 1; front++)
        {
            if (str[front] == ' ') frontIndexToPass++;
            else break;
        }
    }

    if (str[len - 1] == ' ')
    {
        for (int end = len - 1; end >= 0; end--)
        {
            if (str[end] == ' ') endIndexToPass++;
            else break;
        }
    }

    if (tolower(str[0 + frontIndexToPass]) == tolower(str[len - endIndexToPass - 1]))
    {
        if (len <= 2) return 1;
        else
            test_palindrom_rekursiv(str + frontIndexToPass + 1,
                len - endIndexToPass - frontIndexToPass - 2);
    }
    else return 0;
}

Answer 8

我想在这里提供 Python 版本：

 def ispalindrome(word):
     if len(word) < 2: return True

     if word[0] != word[-1]:         # base condition
        return False

     return ispalindrome(word[1:-1]) # chop head/tail each loop

>>> ispalindrome('racecar')
True
>>> ispalindrome('racekcar')
False
>>> ispalindrome('a')
True
>>> ispalindrome('aba')
True

回文校验的递归方法

Recursive method for palindrome checkup

c

algorithm

recursion

palindrome