递归函数不能返回布尔值

Question

我想写返回true的Python函数一个字符串s是回文，也就是等于它的反。例如,“赛车”和“abba”是回文。到目前为止，这是我不成功的尝试。

 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

现在我完全理解为什么会产生上述错误。这是因为一些递归函数返回一个boool并尝试将其添加到字符串中;但是我做不到的是如何避免这个错误。

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)

因为在得到答案之前，您可能会耗尽堆栈空间:-)