python - 在 python 中使用字典进行动态绑定(bind)？

Question

我知道如何递归地计算斐波那契数列，这非常简单:

def F(n):
  if n == 1 or n == 2:
    return 1
  else:
    return k * F(n-2) + F(n - 1)

但是我确实知道这是极其低效的，因为它必须一次又一次地计算相同的值。解决这个问题的方法是在进行过程中以某种方式存储值。假设您想要第 20 个值。一旦计算出 F(13) 是什么，就可以直接存储和调用它的值，而不是通过所有递归级别来获得相同的答案。

字典是这个问题的一个明显的解决方案。然而，我的答案涉及字典不起作用。

U = {1:1, 2:1}
def F(n):
  global U
  if n in U:
    return U[n]
  else:
    U[n] = F(n - 2) + F(n - 1)

运行此代码后，只需打印 U[n]。

我已经多次运行该逻辑，一切看起来都很好，但我不断收到此错误:

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

每当我尝试大于 3 的数字时。我不知道如何返回 None，但我承认我可能错过了导致问题的字典的某种细微差别。

Answer 1

else 子句中缺少 return 语句。

def F(n):
  global U
  if n in U:
    return U[n]
  else:
    U[n] = F(n - 2) + F(n - 1)
    return U[n]

或简化:

def F(n):
  if n not in U:
    U[n] = F(n - 2) + F(n - 1)
  return U[n]

(不需要全局。)