递归函数中的记忆化

Question

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

我写了一个计算“卡塔兰数”的代码，它可以正常工作，但现在我正在尝试通过使用备忘录字典（称之为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 is 1：1”，然后神秘地停止，但在IDLE中相同的代码会打印“dicatalan is 0：1”。

无论如何，当我试图稍后打印dicatalan时，我收到了{}。

这怎么可能？代码发生了什么？

运行调试器被证明是徒劳的。

有没有想法让字典正常工作？

- jizanthapus

---

我认为您从未在dicatalan中存储0，这是进一步问题的原因。 - sega_sai

缩进代码后，这里的功能正常运行（字典内容、打印输出、结果）。您能否确认在我编辑您的帖子后缩进是否相同？ - mmgp

@mmgp 我可以确认代码对我来说运行良好 :) - Vincenzo Pii

这对我也很有效。有一个库可以在functools中进行记忆化：https://dev59.com/Wmgt5IYBdhLWcg3wygab#12562777 - Andy Hayden

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]

- wim

---

大家好，我现在感觉很有趣。可能问题源于错误的语法（dicatalan[(n)])...在复制缩进代码后（感谢mmgp）- 现在它对我也起作用了。sega_sai - 你是对的，但它并没有造成应有的结果...wim - 非常优雅，可爱。非常感谢大家。 - jizanthapus

@user1868486 仅作澄清：dicatalan[(n)] 和 dicatalan[n] 是完全等价的，所以这不是导致问题的原因。此外，我没有进行此更改，它是由其他人进一步编辑的。但是，我将缩进更改为我认为合理的方式，因此如果您仍然拥有原始代码，可以将其与我的缩进编辑进行比较（您可以通过点击帖子底部的“X小时前编辑”链接来查看所做的编辑）。 - mmgp