Рекурсивная функция не может вернуть boolean

Question

Я хочу написать функцию Python, которая возвращает true, строка s является палиндром, то есть равна его обратному. Например, «гоночный автомобиль» и «абба» - это палиндромы. Пока это моя неудачная попытка.

def ispalindrome(s): 
    if len(s) == 1: 
     return s 
    else: 
     reverse = s[-1] + ispalindrome(s[:-1]) 

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

def ispalindrome(s): 
    if len(s) == 1: 
     return s 
    else: 
     reverse = s[-1] + ispalindrome(s[:-1]) 
     return a == reverse 

с помощью функции выше создает следующую ошибку

>>>ispalindrome('racecar') 
Traceback (most recent call last): 
    File "<pyshell#0>", line 1, in <module> 
    ispalindrome('racecar') 
    File "/Users/Nadir/Desktop/Untitled.py", line 24, in ispalindrome 
    reverse = s[-1] + ispalindrome(s[:-1]) 
    File "/Users/Nadir/Desktop/Untitled.py", line 24, in ispalindrome 
    reverse = s[-1] + ispalindrome(s[:-1]) 
    File "/Users/Nadir/Desktop/Untitled.py", line 24, in ispalindrome 
    reverse = s[-1] + ispalindrome(s[:-1]) 
    File "/Users/Nadir/Desktop/Untitled.py", line 24, in ispalindrome 
    reverse = s[-1] + ispalindrome(s[:-1]) 
    File "/Users/Nadir/Desktop/Untitled.py", line 24, in ispalindrome 
    reverse = s[-1] + ispalindrome(s[:-1]) 
TypeError: Can't convert 'bool' object to str implicitly 

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

Answer 1

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

def isPalindrome(s): 
    if len(s) < 2: 
     return True 
    if s[0] != s[-1]: 
     return False 
    return isPalindrome(s[1:-1]) 

print isPalindrome("racecar") 

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

def isPalindrome(orig, reduced, reversed): 
    if reduced == "": 
     return orig == reversed 
    return isPalindrome(orig, reduced[1:], reduced[0] + reversed) 

print isPalindrome("racecar", "racecar", "") 

---

Конечно, вся идея сделать это рекурсивно несовершенна, на что, кроме образования (так как образование, вероятно, ваша цель здесь, это хорошо в качестве примера).

Но имейте в виду, что наилучшие варианты использования для рекурсии - это то, где вы можете избавиться от большого фрагмента «пространства решений» с каждым рекурсивным вызовом (засвидетельствовать бинарный поиск, который может удалять половину оставшегося пространства каждый раз) ,

достаточно большая строки для рекурсивной функции палиндромности будет иметь тот же эффект, что и следующую функция классических случае плохого выбора алгоритма в рекурсивной арене:

def add(unsigned a, unsigned b): 
    if b == 0: 
     return a 
    return add(a+1, b-1) 

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