Рекурсивная функция для сравнения строк без библиотечных функций

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

Причина в том, что s1 и s2 одинаковы в рекурсии.Что я имею в виду: если у вас есть char *s1 = "Hello"; и char *s2 == Elloh, ваши рекурсивные вызовы одинаковы.вы начинаете с одной и той же точки, всегда, вы не пропускаете приращения никаким образом (n, p), поэтому вы в основном начинаете с одной и той же точки при каждом рекурсивном вызове.Что вы можете сделать, это увеличить указатель, и вот краткое решение:

int revisedStrcmp (char *s1, char *s2) {
    if (*s1 == *s2)
        return *s1 == '\0' ? 0 : revisedStrcmp(s1 + 1, s2 + 1);

    return (*s1 > *s2) ? 1 : -1; 
}                                                                                                    

или вы можете сделать следующее:

return revisedStrcmp(s1+i, s2+i);

Answer 2

Основная проблема в вашей функции заключается в том, что вы не передаете обновленные указатели в рекурсивном вызове на 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 вместо простых 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);
}

Answer 3

В части:

    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 rStrcmp(s1,s2);

вы звоните rStrcmp(s1,s2); с s1 и s2, однако вы только что обработали персонажа.Звоните rStrcmp(s1+1,s2+1);.

---

Примечание: поскольку ваша функция обрабатывает только один символ на вызов, вам не нужно индексировать строки с помощью i.Это всегда 0, кроме перед оператором возврата, поэтому его значение никогда не используется:

int rStrcmp(char *s1, char *s2)
{
    if (*s1 =='\0' && *s2 !='\0') //s1 shorter than s2
        return -1;

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

    else if (*s1 !='\0' && *s2 !='\0')  //both not equal to null
    {
        if (*s1>*s2)  return 1; //s1
        else if (*s1<*s2) return -1; //s2
        else
            return rStrcmp(s1+1,s2+1);
    }
    else    //if s1[i] & s2[i] are null
    {
        // since both are null, they are the same length and each
        // character was the same: equal
        return 0;
    }
}

Answer 4

Просто измените return rStrcmp(s1, s2); на return rStrcmp(s1+i, s2+i);.Таким образом, вы сохраняете приращения позиции вашего массива.

Answer 5

Вы не передаете в функцию переменные i, n, p.Таким образом, ваша функция не закончится, потому что она будет запускаться каждый раз с переменными счетчика в 0.