c 递归函数检查字符串是否是回文

问题描述 投票：0回答：5

我正在用 C 编程语言做一个项目，其中一项任务要求我递归地检查字符串是否是回文。我写了一些代码，但没有得到正确的输出。以下是管理该任务的一些规则：

  1. 如果字符串是回文，则返回1，否则返回0。
  2. 如果字符串为空，则返回 1。 这是我使用的代码：
int is_palindrome(char *s)
{
    int len;

    len = strlen(s);
    if (len == 0 || len == 1)
        return (0);

    if (*s != s[len - 1])
        return (1);

    return is_palindrome(s + 1);
}

这是我的驱动程序代码：

#include "main.h"
#include <stdio.h>

/**
 * main - check the code
 *
 * Return: Always 0.
 */
int main(void)
{
    int r;

    r = is_palindrome("level");
    printf("%d\n", r);
    r = is_palindrome("redder");
    printf("%d\n", r);
    r = is_palindrome("test");
    printf("%d\n", r);
    r = is_palindrome("step on no pets");
    printf("%d\n", r);
    return (0);
}

注意：所有声明都在 main.h 文件中

我得到的输出始终是1，代码在一定程度上工作正常，因为我使用了如果第一个字符与最后一个字符相同，则它是回文的原则。但我希望它适用于所有情况，例如偶数字符串的情况。

我应该如何修复代码才能正常工作？谢谢你

c function recursion c-strings palindrome
5个回答
1
投票

问题1：

if (*s != s[len - 1]) return (1);
没有任何意义，它应该返回零（假）。

问题2：

return is_palindrome(s + 1);
只能从前面迭代，还需要从后面迭代。

您也可以通过传递长度来修复它。您可以将 strlen 调用移到递归之外（这也可以提高性能）并传递长度。

但是，如果您只是传递指向第一个和最后一个字母的指针，然后递增/递减直到指针相遇，那么实现起来会变得更加容易和可读：

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

static bool check_palindrome (const char* start, const char* end)
{
   if(start >= end)     // pointers have met in the middle without differences detected
     return true;
   if (*start != *end)  // values differ at some point, stop here
     return false;

   return check_palindrome(start+1, end-1);
}

bool is_palindrome (const char *s)
{
    size_t length = strlen(s);
    if(length == 0)
      return true;
    return check_palindrome (s, s+length-1);
}

int main(void) 
{
  printf("%d\n", is_palindrome("level"));
  printf("%d\n", is_palindrome("redder"));
  printf("%d\n", is_palindrome("test"));
}

还请注意，递归在这里绝对没有任何作用，循环总是更好。在这种特定情况下，很容易将递归实现为“尾调用”，但情况并非总是如此。如果不是这样，递归总是不必要的危险和缓慢，绝对不会有任何收获。

在 gcc 13.1 x86_64 上进行基准测试

-O3
，请注意机器代码中没有递归调用：

is_palindrome:
        push    rbx
        mov     rbx, rdi
        call    strlen
        xor     edx, edx
        test    rax, rax
        je      .L1
        lea     rax, [rbx-1+rax]
        cmp     rbx, rax
        jb      .L3
        jmp     .L5
.L11:
        sub     rax, 1
        add     rbx, 1
        cmp     rbx, rax
        jnb     .L5
.L3:
        movzx   ecx, BYTE PTR [rax]
        cmp     BYTE PTR [rbx], cl
        je      .L11
        xor     edx, edx
.L1:
        mov     eax, edx
        pop     rbx
        ret
.L5:
        mov     edx, 1
        pop     rbx
        mov     eax, edx
        ret
1
投票

该函数的递归调用

return is_palindrome(s + 1);

由于此语句，结果检查字符串中的所有字符是否等于最后一个字符

if (*s != s[len - 1])

还有这个 if 语句

if (len == 0 || len == 1)
    return (0);

与赋值的描述相矛盾，因为对于空字符串，函数应返回 

1
。

您可以编写例如引入辅助函数

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

int is_palindrome( const char *s)
{
    return is_palindrome_rec( s, strlen( s ) );
}

另一种方法是在函数内使用静态变量，如下面的演示程序所示。尽管这种方法效率低下，因为在每次递归调用中都会调用函数

strlen
。然而，记住替代方法总是有用的。

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

int is_palindrome( const char *s )
{
    static size_t offset = 0;

    size_t n = strlen( s );

    if ( n - offset < 2 ) 
    {
        return 1;
    }
    else if ( s[offset] != s[n - offset - 1] )
    {
        return 0;
    } 
    else
    {
        ++offset;
        int result = is_palindrome( s );
        --offset;

        return result;
    }
}

int main( void ) 
{
    const char *s = "1";

    printf( "is_palindrome( \"%s\" ) is %s\n",
        s, is_palindrome( s ) ? "true" : "false" );

    s = "11";

    printf( "is_palindrome( \"%s\" ) is %s\n",
        s, is_palindrome( s ) ? "true" : "false" );

    s = "121";

    printf( "is_palindrome( \"%s\" ) is %s\n",
        s, is_palindrome( s ) ? "true" : "false" );

    s = "122";

    printf( "is_palindrome( \"%s\" ) is %s\n",
        s, is_palindrome( s ) ? "true" : "false" );
}

程序输出为

is_palindrome( "1" ) is true
is_palindrome( "11" ) is true
is_palindrome( "121" ) is true
is_palindrome( "122" ) is false
0
投票

您的程序中有多个错误。

首先，回文的返回值是相反的。

int is_palindrome(char *s)
{
    int len = strlen(s);
    if (len == 0 || len == 1)
        return 1;  // Empty string or 1char string are treated as palindromes

    if (*s != s[len - 1])
        return 0;  // If they do not match, no palindrome.

    // Not sure yet, lets look into the other characters.
    return is_palindrome(s + 1);
}

此外，您可以前进到字符串开头的下一个字符，但保持最后一个字符不变。 有两个选项可以解决这个问题。两者都有不同的优点和缺点。

变体 1：传递长度参数：

int is_palindrome(char *s, size_t len)
{
    if (len == 0 || len == 1)
        return 1;  // Empty string or 1char string are treated as palindromes

    if (*s != s[len - 1])
        return 0;  // If they do not match, no palindrome.

    // Not sure yet, lets look into the other characters.
    return is_palindrome(s+1, len-2);
}

int main(void)
{
    int r;
    char *string;

    string = "level";
    r = is_palindrome(string, strlen(string));
    printf("%d\n", r);

    string = "redder";
    r = is_palindrome(string, strlen(string));
    printf("%d\n", r);

    string = "test";
    r = is_palindrome(string, strlen(string));
    printf("%d\n", r);

    string = "step on no pets";
    r = is_palindrome(string, strlen(string));
    printf("%d\n", r);

    return 0;
}

这需要更改函数的签名。根据您的任务，这可能是不允许的。

变体 2：删除最后一个字符：

int is_palindrome(char *s)
{
    size_t len = strlen(s);

    if (len == 0 || len == 1)
        return 1;  // Empty string or 1char string are treated as palindromes

    if (*s != s[len - 1])
        return 0;  // If they do not match, no palindrome.

    // Not sure yet, lets look into the other characters.
    s[len-1] = 0; //Chop last character
    return is_palindrome(s+1);
}

int main(void)
{
    int r;
    char string[100];

    strcpy(string,"level");
    r = is_palindrome(string);
    printf("%d\n", r);

    strcpy(string,"redder");
    r = is_palindrome(string);
    printf("%d\n", r);

    strcpy(string,"test");
    r = is_palindrome(string);
    printf("%d\n", r);

    strcpy(string,"step on no pets");
    r = is_palindrome(string);
    printf("%d\n", r);

    return 0;
}

此变体要求您可以修改传递的字符串参数。这对于字符串文字是不允许的。

0
投票

在您的代码中，您的真值是相反的，并且您总是与字符串中的最后一个字符进行比较。这是一个工作版本：

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

int Palindromic1(const char s[], int len)
{
    int result;

    if (len <= 1) {
        result = 1;
    } else if (toupper(s[0]) != toupper(s[len - 1])) {
        result = 0;
    } else {
        result = Palindromic1(s + 1, len - 2);
    }
    return result;
}


int Palindromic(const char s[])
{
    return Palindromic1(s, strlen(s));
}


int main(void)
{
    assert(Palindromic(""));
    assert(Palindromic("a"));
    assert(Palindromic("aba"));
    assert(! Palindromic("abb"));
    assert(Palindromic("abba"));
    assert(! Palindromic("abab"));
    assert(Palindromic("Able was I ere I saw Elba"));
    return 0;
}
0
投票

我相信已经很清楚了，每次调用时字符串的 end 必须回退 1。 您也不应该更改字符串，因为它可以是像 

is_palindrome("a thing")
中那样的文字。无论如何，您不应该更改该字符串：原始形式的其他地方可能需要它，因为调用者只是想知道该字符串是否是回文。

当然，这里的递归是一种浪费，但使用递归来编写它是一个常见的作业，因为它简单且说明性。

在接下来的几行中，我将尝试说明原因。并且还留下了完整的例子。

迭代版本

int isPal(const char* str)
{
    char*  p    = (char*)str;
    size_t size = 0;
    while (*p++ != 0)++ size;  // strlen
    for (size_t i = 0; i < size / 2; i += 1)
        if (*(str + i) != *(str + size - i - 1))
            return 0;  // false
    return 1; // all equal: palindrome
}

这里

  • while
    循环计算大小，因此不需要
    string.h
  • for
    循环放大字符串以查看它是否是回文。

递归版本

如果可以更改签名，我们可以将初始大小作为参数传递

int isPal_r(const char* str, const size_t size)
{
    if (size < 2) return 1;  // trivial
    if (*str != *(str + size - 1)) return 0; 
    return isPal_r(str + 1, size - 2);  // try inner string
}

在这里，我们看到 

while
循环如何消失，因为 
size
在第一次调用时传递。 以及 
for
循环如何消失，并被递归调用所取代。 这就是为什么这种回文检查以及不可避免的阶乘评估经常在引入递归时出现。

如何不更改签名

一种可能的方法是使用 2 个 

static
值：

  • 原字符串没有变化
  • 不需要第二个参数
  • 无需调用 
    strlen
    或在每次调用时计算大小
  • 一种方法重置功能，以便可以在同一程序中重复使用
int is_Pal(const char* str)
{
    static char first = 1;
    static long size  = 0;
    if (first != 0)
    {
        const char* p = str;
        while (*p++ != 0) ++size;  // strlen
        first = 0; // now false
    }
    else
        size -= 2;

    if (size < 2)
    {   first = 1, size = 0;  // reset
        return 1;             // trivial
    }

    if (*str != *(str + size - 1))
    {   first = 1, size = 0;  // reset
        return 0;
    }
    return is_Pal(str + 1);  // try inner string
}

这个就可以了。

测试

SO C> p 1 11 axa "" abcdxba "123454321 1221 123454321"
     6 arguments.
     Return 1 for a palindrome, or 0


string is "1"
     isPal_r() returned 1

string is "11"
     isPal_r() returned 1

string is "axa"
     isPal_r() returned 1

string is ""
     isPal_r() returned 1

string is "abcdxba"
     isPal_r() returned 0

string is "123454321 1221 123454321"
     isPal_r() returned 1
 
SO C> p

Please enter strings on the command line: Usage: program str1 str2 ...

SO C>

本次测试的源代码

#include <stdio.h>

int  is_Pal(const char*);
void test_isPal(const char*);

int main(int argc, char** argv)
{
    if (argc < 2)
    {
        fprintf(
            stderr,
            "\nPlease enter strings on the command line: "
            "Usage: program "
            "str1 str2 ...\n");
        return -1;
    }
    fprintf(
        stderr,
        "     %d arguments.\n     Return 1 for a "
        "palindrome, or 0\n\n",
        argc - 1);
    for (size_t i = 1; i < argc; i += 1)
        test_isPal(argv[i]);
    return 0;
}

void test_isPal(const char* str)
{
    if (str == NULL) return;
    fprintf(stderr, "\nstring is \"%s\"\n", str);
    char*  p    = (char*)str;
    int res = is_Pal(str);
    fprintf(stderr, "     isPal_r() returned %d\n", res);
}

int is_Pal(const char* str)
{
    static char first = 1;
    static long size  = 0;
    if (first != 0)
    {
        const char* p = str;
        while (*p++ != 0) ++size;  // strlen
        first = 0; // now false
    }
    else
        size -= 2;

    if (size < 2)
    {
        first = 1, size = 0;  // reset
        return 1;             // trivial
    }

    if (*str != *(str + size - 1))
    {
        first = 1, size = 0;  // reset
        return 0;
    }
    return is_Pal(str + 1);  // try inner string
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.