Как я могу использовать рекурсию, чтобы найти палиндромы с помощью Python?

Question

Я только начал изучать чудеса программирования. Я пытаюсь написать код для идентификации числовых палиндромов. Просто смотрю на цифры, а не на тексты. Я пытаюсь научиться использовать рекурсию здесь. Но я просто никуда не денусь и не могу понять, что с этим не так.

Моя идея состояла в том, чтобы проверить первую строку против последней, затем удалить эти две, если они совпадают, и повторить. В конце концов ничего не останется (подразумевается, что это палиндром), или будет пара, которая не соответствует (подразумевается обратное).

Я знаю, что есть лучшие коды для поиска палиндромов, но я просто хотел попробовать свои силы в рекурсии.

Так что не так?

def f(n):
    global li   
    li=list(str(n))
    if (len(li)==(1 or 0)):
        return True
    elif li[len(li)-1]==li[0]:
        del li[0]
        del li[len(li)-1]
        if len(li)==0:
            return True
        if len(li)>0:
            global x
            x=''.join(li)
            str(x)
            f(x)
    else:
      return False

Заранее спасибо!

Answer 1

Несколько комментариев

• Почему глобалы x и li?В рекурсии все переменные должны быть локальными.
• Почему вы конвертируете назад и вперед между str и list?Вы можете подписать оба из них
• Вам необходимо вернуть результат вашего рекурсивного вызова: return f(x)

Попробуйте эти предложения и посмотрите, как это работаетвне.

Answer 2

Есть несколько проблем с вашим решением. Позвольте мне проанализировать их построчно.

1. Вам не нужны global операторы, если вы не собираетесь изменять переменные вне области действия функции. Таким образом, я удалил две строки с global из вашего кода.

2. li=list(str(n)): приведение строки к списку не требуется, поскольку строка в Python имеет интерфейс, аналогичный неизменяемому списку. Так что простого li = str(n) будет достаточно.

3. if (len(li)==(1 or 0)):: хотя все выглядит хорошо, на самом деле это неверный способ сравнения значения с несколькими другими значениями. Оператор or возвращает первое «истинное» значение из своего левого или правого операнда, поэтому в этом случае он всегда возвращает 1. Вместо этого вы можете использовать оператор in, который проверяет, является ли левый операнд элементом правого операнда. Если мы сделаем правильный операнд кортежем (1, 0), все будет хорошо. Кроме того, вам не нужны скобки вокруг оператора if. Вы должны написать: if len(li) in (1, 0):

4. elif li[len(li)-1]==li[0]: хорошо, но мы можем написать это короче на Python, потому что он поддерживает индексацию отрицательного списка: elif li[-1] == li[0]:

5. Поскольку мы не используем списки (изменяемые последовательности) из-за пункта 2. мы не можем сделать del li[0] для них. И в любом случае, удаление первого элемента списка в Python очень неэффективно (весь список должен быть скопирован). По той же причине мы не можем сделать del li[len(li)-1]. Вместо этого мы можем использовать оператор «сплайсинга» для извлечения подстроки из строки: li = li[1:-1]

6. if len(li)==0: не нужно долго. В Python пустые строки и списки преобразуются в False, если проверено if. Таким образом, вы можете написать if not li:

7. if len(li)>0:: Вам не нужно снова проверять, не является ли li не пустым - вы проверили его в пункте 6. Так что простого else: будет достаточно. Или, что еще лучше, удалите эту строку полностью и удалите отступ для остальной части функции, потому что тело if в 6. содержит return. Поэтому, если мы не ввели if, мы находимся в else, не написав его вообще.

8. x=''.join(li): нам не нужно преобразовывать нашу строку в строку из-за решения, принятого в 2. Удалите эту строку.

9. str(x): эта строка не принесла ничего полезного в вашем коде, потому что str() не изменяет свой аргумент на месте, но возвращает новое значение (поэтому x = str(x) будет иметь больше смысла) , Вы также можете удалить его.

10. f(x): Это допустимый способ вызова рекурсивной функции в Python, но вы должны что-то сделать с ее значением. Вернуть это возможно? Мы изменим его на: return f(li) (поскольку у нас больше нет переменной x).

Мы получаем следующий код:

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        if not li:
            return True
        return f(li)
    else:
        return False

Это почти то, что нам нужно, но все же можно внести небольшие уточнения. Если вы посмотрите на строки if not li: return True, вы увидите, что они не нужны. Если мы удалим их, то f будет вызываться с пустой строкой в ​​качестве аргумента, len(li) будет равно 0 и True будет возвращено в любом случае. Итак, мы продолжим и удалим эти строки:

def f(n):
    li = str(n)
    if len(li) in (1, 0):
        return True
    elif li[-1] == li[0]:
        li = li[1:-1]
        return f(li)
    else:
        return False

И это все! Удачи на пути к тому, чтобы стать успешным программистом!

Answer 3

Прежде чем заглядывать в это слишком много, if (len(li)==(1 or 0)): не делает то, что вы ожидаете.(1 or 0) всегда будет иметь значение 1.

Возможно, вы захотите:

if len(li) in (1, 0):

Answer 4

Разделите все шоу в список, а затем просто:

def fun(yourList):
    if yourList.pop(0) == yourList.pop(-1):
        if len(yourList) < 2:
            return True # We're a palindrome
        else:
            return fun(yourList)
    else:
        return False # We're not a palindrome

print "1234321"
print fun(list("1234321")) # True
print "6234321"
print fun(list("6234321")) # False

Answer 5

number = int(raw_input("Enter a number: "))

rev = 0
neg = number

original = number


if (number < 0):
    number = number * -1

else:

    number = number

while ( number > 0 ):

     k = number % 10

     number = number / 10

     rev = k + ( rev * 10 )

     if (number < 1):
         break

if ( neg < 0 ):
    rev =  ( rev * -1)

else:

    rev = (rev)

if ( rev == original):

    print "The number you entered is a palindrome number"

else:

    print "The number you entered is not a palindrome number"

Этот код работает даже для отрицательных чисел, я новичок в программировании в случае каких-либо ошибок не возражаю.

Answer 6

def palindrome(n):
    return n == n[::-1]

Answer 7

Трудно сказать, что вы собираетесь делать из своего кода, но я написал более простой (также рекурсивный) пример, который может помочь вам понять:

def is_palindrome(num):
    s = str(num)
    if s[0] != s[-1]:
       return False
    elif not s[1:-1]:
       return True
    else:
       return is_palindrome(int(s[1:-1]))