Блог

Главная - Вопросы по программированию - Использование рекурсии для определения, является ли слово палиндромом

Использование рекурсии для определения, является ли слово палиндромом

#python

#python

Вопрос:

Я пытаюсь определить, является ли данное слово палиндромом.

Цель моего кода состоит в том, чтобы функция взяла слово и удалила из него все знаки препинания или пробелы. Если длина слова равна 0 или 1, возвращается, что слово является палиндромом. Затем я проверяю, совпадают ли первая и последняя буквы. Если это не так, возвращается, что это не палиндром. Если первая и последняя буквы совпадают, я хочу заменить эти две буквы пробелами и снова вызвать свою функцию. Причина, по которой я заменяю буквы пробелами, заключается в том, что оно будет отредактировано моими первоначальными операторами редактирования.

 def palindrome(word):
    editWord = word.strip(" ").strip("!").strip("?")

    stringOne = "A palindrome"
    stringTwo = "Not a palindrome"

    if len(editWord) == 0 or len(editWord) == 1:
        return stringOne

    elif editWord[0] != editWord[-1]:
        return stringTwo

    else:
        word = editWord.replace(editWord[0], " ").replace(editWord[-1], " ")
        palindrome(word)
        return stringOne

print(palindrome("area"))

При тестировании с использованием отдельных букв он работает правильно, а также, если я тестирую такие слова, как «are», что, очевидно, не является палиндромом. Однако, если я вызываю слово area, оно возвращает «палиндром», когда это не так. Это создает впечатление, что оно больше не вызывает мою функцию. Любые предложения о том, почему это происходит?

Комментарии:

1. replace ведет себя не так, как вы ожидаете. Это глобальная замена — каждый экземпляр первого параметра заменяется вторым.

2. Вместо того, чтобы искусственно удалять слово, почему бы просто не выполнить рекурсию по подстроке?

3. Кроме того, вы вызываете palindrome(word) , но затем полностью игнорируете возвращаемое значение…

4. @MadPhysicist, не могли бы вы расширить рекурсию по подстроке? Я новичок в рекурсии

5. Безумный физик понял это правильно в своем втором комментарии. Ваш код рекурсивен, но вы никогда не используете stringOne or, stringTwo возвращаемый цепочкой рекурсивных вызовов; вместо этого вы безоговорочно возвращаетесь stringOne после рекурсивного вызова palindrome . Это означает, что любое слово, которое приводит к принятию ветви else при первом вызове palindrome taken, будет считаться палиндромным.

Ответ №1:

Чтобы рекурсия работала здесь должным образом, в вашем заявлении else должно быть сказано что-то вроде «слово является палиндромом, если внешние символы равны, а остаток также является палиндромом». Вместо этого ваш код заменяет все вхождения внешних символов пробелами, проверяет, является ли слово палиндромом, и игнорирует результат, чтобы всегда возвращать «да».

Вы можете выполнить правильную рекурсию, используя нарезку вместо замены:

 else:
    return palindrome(editWord[1:-1])

Ответ №2:

Еще одна альтернатива замене букв при одновременном выполнении этого рекурсивно, чтобы отслеживать индекс в слове и увеличивать его при рекурсии. Это избавляет вас от необходимости создавать новые фрагменты при каждой рекурсии. В этом случае ваш крайний случай будет, когда индекс находится в середине слова.

 def palindrome(word, i = 0):
    if i >= len(word)//2:
        return True
    if word[i] != word[-(i 1)]:
        return False
    return palindrome(word, i 1)

palindrome("mrowlatemymetalworm") # true
Метки: