c - 递归函数比较没有库函数的字符串

Question

我应该用 C 编程语言编写一个递归函数，检查字符串 1 是否大于等于或小于字符串 2，从而返回 1、0, -1 分别。

下面是我编写的代码。该程序无法终止，我无法找出原因。请给我一些建议。谢谢。

int revisedStrcmp(char *s1, char *s2) {
    int i = 0, n = 0, p = 0;

    if (s1[i] == '\0' && s2[i] != '\0') //s1 shorter than s2
        return -1;

    else if (s1[i] != '\0' && s2[i] == '\0') //s1 longer than s2
        return 1;

    else if (s1[i] != '\0' && s2[i] != '\0')  //both not equal to null
    {
        if (s1[i] > s2[i])  n += 1; //s1
        else if (s1[i] < s2[i]) p += 1; //s2
        else
        {
           n += 1; //s1
           p += 1; //s2
        }
        i += 1;
        return revisedStrcmp(s1, s2);
    }
    else    //if s1[i] & s2[i] are null
    {
        if (n > p) //s1 > s2
            return 1;
        else if (n < p)
            return -1;
        else
            return 0;
    }
}

Answer 1

您的函数中的主要问题是您没有在对 revisedStrcmp 的递归调用中传递更新的指针，从而导致无限循环和潜在的堆栈溢出。

这是一个更正和简化的版本:

int revisedStrcmp(const char *s1, const char *s2) {
    if (*s1 < *s2)
        return -1;
    if (*s1 > *s2)
        return +1;
    // *s1 == *s2
    if (*s1 == '\0')
        return 0;
    return revisedStrcmp(s1 + 1, s2 + 1);
}

不需要为较短的字符串做特殊情况，因为可以在比较中使用空终止符。

这种特殊的递归风格称为尾递归，现代编译器会将其编译成循环。

但是请注意，要使 revisedStrcmp() 返回与 strcmp 相同的顺序，必须对 unsigned char 值执行比较，而不是plain char，可以在许多架构上默认签名:

int revisedStrcmp(const char *s1, const char *s2) {
    unsigned char c1 = *s1, c2 = *s2;
    if (c1 < c2)
        return -1;
    if (c1 > c2)
        return +1;
    // c1 == c2
    if (c1 == '\0')
        return 0;
    return revisedStrcmp(s1 + 1, s2 + 1);
}