突破遞歸函數？

我想知道如何擺脫主函數的遞歸循環。我正在嘗試做一個簡單的迴文練習。函數應該爲「redivider」返回True，但是返回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")

來源

2012-05-11 Chris

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。我還排除了一個冗餘的條件，並檢查了長度相等的迴文邊緣情況。

來源

2012-05-11 02:18:20

你需要來回報您的遞歸調用的結果，而你也需要添加一個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

來源

2012-05-11 02:15:11

你錯過了一個回報。另外，請勿使用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")

來源

2012-05-11 02:17:19 jgritty

如果它們不匹配並且添加返回語句，則需要返回False。此外，您可能需要檢查len（str）== 0和len（str）== 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

來源

2012-05-11 02:18:32 Qlaus

@ li.davidm：你快了:) – Qlaus

您不會「斷開」遞歸函數。試圖這樣做，說你在錯誤地思考他們。目前你的遞歸調用忽略了輸出，這意味着遞歸是毫無意義的;不管is_pal(middle(str))返回對函數的返回值沒有影響。

遞歸算法通過將問題分解爲更小的問題，遞歸地解決較小的問題，然後使用較小的解決方案爲較大的問題構建正確的解決方案來解決輸入問題。您不會「打破」內部呼叫，您將解決方案返回到一個級別。你不知道（或者需要知道）需要知道你是在進行內線呼叫還是在頂級呼叫。無論哪種情況，你的函數都應該做同樣的事情：如果參數是迴文，則返回True，否則返回False。

你想實現的算法基本上是這樣的：

如果字符串的長度爲1，這是一個迴文（返回True）
否則，如果第一個字符是一樣的最後一個字符，那麼如果中間字符是迴文，則輸入是迴文。

那麼這是什麼意思是，一旦你建立了第一個和最後一個字符是相同的，回答「是我輸入一個迴文」是一模一樣的答案爲「是中間字符迴文「。您需要返回該答案以履行您的合同。所以遞歸調用應該是return is_pal(middle(str))而不僅僅是is_pal(middle(str))。如果這是最高級別的通話，那就是答案。如果這個不是頂級呼叫，那麼外部呼叫將需要這個答案來解決外部問題的答案（在這種情況下，只需返回它）。

順便說一句，你的算法也有一些其他的問題。

你有去無回False，所以答案永遠不能False（在這種情況下，你恰巧脫落，如果第一個和最後一個字符不匹配函數的最後意外地返回None和None會大多數情況下可能會作爲False的替代品，但它仍然不是正確的）。
如果字符串的長度爲零，而不是1（如果連長度的迴文結構傳遞一次相等的第一和最後一個字符的所有對剝去如果一個空字符串在或通過將發生），那麼你不會返回正確的答案，實際上你會嘗試獲取空字符串的第一個和最後一個字符，這將導致異常。

來源

2012-05-11 02:31:08 Ben

突破遞歸函數？

回答

相關問題