遞歸函數無法返回布爾型

我想寫一個Python函數，它返回true一個字符串s是一個迴文，即它等於它的反向。例如'racecar'和'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

現在我完全理解爲什麼上述錯誤產生。這是因爲一些遞歸函數返回一個布爾值並嘗試將其添加到一個字符串;但我不能做的是如何避免這個錯誤。

來源

2015-02-12 TheValars

爲什麼不直接測試第一個和最後一個字符，並在遞歸之前將它們關閉？ – 2015-02-12 03:29:32

我可以，但我正在尋找一種方法，我可以使用生成的「反向」。 – TheValars 2015-02-12 03:32:25

一個更好的迴文測試可能只是爲了確保結束字符是相同的，然後內部字符也是迴文，終止條件以零或一個字符的字符串結尾（這是，是定義，迴文）：

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)

中，你可能

在獲得答案之前很久就用完了堆棧空間:-)

來源

2015-02-12 03:40:33 paxdiablo

遞歸函數無法返回布爾型

回答

相關問題