递归函数的记忆化

Question

我遇到了一个奇怪的现象：

我写了一个代码来计算“Catalan数字”，这是可行的，但现在我正试图通过使用一个记忆字典（称为dictalan）来改进运行时：

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-for n=1代码运行到一半并按预期打印：“didalan是1:1”，然后神秘地停止，但在空闲时，相同的代码会打印“indicatalan是0:1”。在

任何情况下，当我稍后试图打印时，我收到了{}。在

怎么可能呢？代码中会发生什么？ 运行调试器证明是徒劳的。在

有什么办法让这句话发挥作用吗？在

Answer 1

对我来说也很好，我随意简化了你的代码：

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]