递归函数不能 return 布尔值

Question

我想写Python函数returns true 一个字符串s是一个回文，也就是说，它等于它的倒数。例如 'racecar' 和 'abba' 是回文。到目前为止，这是我不成功的尝试。

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

当我告诉我的函数 return 相反时，我没有问题，但是，我很困惑我应该如何进行比较才能 return 布尔值。

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

现在我完全明白为什么会出现上面的错误了。这是因为一些递归函数 return 一个 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")

当你只能弄乱 one 结尾的字符串时，尝试为这个问题创建一个优雅的递归解决方案是相当困难的，因为你需要传递用于比较的原始字符串，您当前正在反转的字符串的剩余部分，以及迄今为止反转的字符串，例如：

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

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

当然，递归执行此操作的整个想法是有缺陷的，除了教育（因为教育可能是您的目标，举个例子也没关系）。

但请记住，递归的最佳用例是您可以在每次递归调用时处理大块 "solution space"（以二分查找为例，它可以处理剩余的一半 space每次）。

递归回文函数的足够大的字符串将与以下函数具有相同的效果，经典递归领域算法选择不佳的情况：

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

因为你很可能运行在你得到答案之前很久 space :-)

递归函数不能 return 布尔值

Recursive function cannot return a boolean

recursion

boolean

python-3.x