記憶化的遞歸函數

我遇到了一個奇怪的現象：記憶化的遞歸函數

我寫了一個代碼來計算「加泰羅尼亞號」，其工作，但現在我想通過使用記憶化的字典，以提高運行時（稱爲它dicatalan）：

dicatalan = {} 
def catalan(n): 
    if n == 0: 
     return 1 
    else: 
     res = 0 
     if n not in dicatalan: 
      for i in range(n): 
       res += catalan(i) * catalan(n - i - 1) 
      dicatalan[n] = res 
      print ("dicatalan is", dicatalan) 
    return dicatalan[n]

這裏的漁獲物 - 在Eclipse - Pydev的 - 爲n=1代碼運行中途打印效果與預期：「dicatalan是1：1」停止神祕之前，但在IDLE同一代碼打印「雙癸酸是0：1「。

任何情況下，當試圖打印稍後我接收到的{} dicatalan。

這怎麼可能？代碼中發生了什麼？運行調試器的證明是徒勞的。

dict有什麼想法嗎？

來源

2012-12-08 jizanthapus

我不認爲你曾經0存儲在dicatalan，這是進一步的問題的原因。 –

縮進代碼後，它在這裏工作得很好（字典內容，印刷品，結果）。您可以確認您的縮進是否與您的帖子上的編輯相同？ – mmgp

@mmgp我可以確認代碼適用於我:) –

對我的作品也沒關係，我把簡化您的代碼一點點的自由：

def catalan(n, memo={0: 1}): 
    if n not in memo: 
    memo[n] = sum((catalan(i) * catalan(n - i - 1)) for i in range(n)) 
    return memo[n]

來源

2012-12-08 14:44:40 wim

大家好，現在我覺得好笑。可能是由於錯誤語法（dicatalan [（n）]）導致的問題...複製縮進代碼後（謝謝mmgp） - 現在它也適用於我。 sega_sai - 你是對的，但它不會造成應得的結果... wim - 非常優雅，可愛的一個。非常感謝大家。 – jizanthapus

@ user1868486只是一個說明：'dicatalan [（n）]'完全等同於'dicatalan [n]'，所以這不是導致問題的原因。另外，我沒有做這個改變，它被別人進一步編輯。但是，我將縮進更改爲我認爲合理的，所以如果您仍然有原始代碼，可以將其與縮進編輯進行比較（您可以通過點擊底部的「編輯X小時前」鏈接查看進行了哪些編輯你的帖子）。 – mmgp

記憶化的遞歸函數

回答

相關問題