Вывод из рекурсивной функции?

Question

Мне интересно, как вырваться из рекурсивного цикла в основную функцию. Я пытаюсь сделать простую операцию палиндрома. Функция должна возвращать True для «redivider», но возвращаемое значение True передается is_pal(), и функция не прерывается. За исключением добавления второй переменной is_pal для отслеживания True/False, каков правильный способ вырваться из этого рекурсивного цикла? Благодарю.

def first(word): 
    return word[0] 

def last(word): 
    return word[-1] 

def middle(word): 
    return word[1:-1] 

def is_pal(str):  
    if len(str) == 1: 
     return True 

    if first(str) == last(str) and len(str) > 1: 
     is_pal(middle(str)) 

print is_pal("redivider") 

Answer 1

def is_pal(str):  
    if len(str) <= 1: 
     return True 

    if first(str) == last(str): 
     return is_pal(middle(str)) 
    else: 
     return False 

Таким образом, если они не совпадают, то False возвращается; если он доходит до конца, возвращается True. Я также устранил избыточное условное выражение и проверял его на краю палиндрома четной длины.

Answer 2

Вы должны вернуть результат вашего рекурсивного вызова, и вы должны также добавить return False, если другие пути не принимаются.

def is_pal(str):  
    if len(str) == 1: 
     return True 

    if first(str) == last(str) and len(str) > 1: 
     return is_pal(middle(str)) 

    return False 

Answer 3

Вам не хватает возврата. Кроме того, не используйте str в качестве имени переменной. Последняя вещь, первая и последняя функции можно назвать немного лучше.

def first_letter(word): 
    return word[0] 

def last_letter(word): 
    return word[-1] 

def middle(word): 
    return word[1:-1] 

def is_pal(word):  
    if len(word) == 1: 
     return True 

    if first_letter(word) == last_letter(word) and len(word) > 1: 
     return is_pal(middle(word)) 

print is_pal("redivider") 

Answer 4

Вам нужно вернуть False, если они не совпадают и добавить оператор возврата. Кроме того, вы, вероятно, хотите, чтобы проверить против LEN (НТР) == 0 и LEN (ул) == 1:

def is_pal(str): 
    if len(str) in [0, 1]: 
     return True 
    if first(str) == last(str) and len(str) > 1: 
     return is_pal(middle(str)) 
    else : 
     return False 

Answer 5

Вы не «сломаться» из рекурсивных функций. Попытка сделать это говорит, что вы думаете о них не так. В настоящее время ваш рекурсивный вызов игнорирует вывод, а это означает, что рекурсия бессмысленна; независимо от того, что is_pal(middle(str)) возвращает, не влияет на возвращаемое значение вашей функции.

Рекурсивный алгоритм решает проблему ввода, разлагая проблему на меньшую задачу, решая результирующее решение меньшей задачи, а затем используя меньшее решение для построения правильного решения более крупной задачи. Вы не «ломаете» внутренние вызовы, вы возвращаете решение на один уровень. Вы не знаете (или должны знать), должны знать, находитесь ли вы во внутреннем вызове или на верхнем уровне. В любом случае ваша функция должна делать то же самое: return True, если аргумент является палиндром и False, если это не так.

алгоритм вы пытаетесь реализовать в основном это:

1. Если строка имеет длину 1, это палиндром (вернуть True)
2. В противном случае, если первый символ такой же, как последний символ, тогда вход является палиндром, если средние символы являются палиндром.

Так что это означает, что как только вы установили первые и последние символы совпадают, то ответ на «мой вход палиндром» является точно так же как ответ на «являются средними персонажи палиндром ". Вы должны вернуть ответ, чтобы выполнить свой контракт. Таким образом, рекурсивный вызов должен быть return is_pal(middle(str)), а не только is_pal(middle(str)). Если это был вызов верхнего уровня, тогда это ответ; если этот не был вызовом верхнего уровня, тогда внешнему вызову понадобится этот ответ, чтобы выработать ответ на внешнюю проблему (в этом случае, просто вернув ее).

---

Btw, ваш алгоритм также имеет некоторые другие проблемы.

1. Вы никогда не вернуться False, так что ответ не может быть False (в этом случае вам случится случайно вернуться None падения с конца функции, если первый и последний символ не совпадает, и None будет вероятно, в большинстве случаев занимают позицию False, но это по-прежнему не совсем правильно).
2. Если длина строки является нулевого, а не 1 (что произойдет, если пустая строка передается в или если палиндром четной длины проходит один раз все пары одинаковых первых и последних символы, извлекают), то вы не вернете правильный ответ, и на самом деле вы пытаетесь получить первый и последний символ пустой строки, что вызовет исключение.