1

假设您想获得第 n 个斐波那契数。然后，一种可能性是使用递归函数

def Fib(n, d):
    """Assumes n is an int >= 0, d dictionary
    Returns nth Fibonacci number"""
    if n in d:
        return d[n]
    else:
        d[n] = Fib(n-1, d) + Fib(n-2, d)
        return d[n]

这工作得很好。我试图将其缩短为

 def Fib(n, d):
        return d.setdefault(n, Fib(n-1, d) + Fib(n-2, d))

但是当我可以用

d={0:1, 1:1}
print(f(2, d))

，或者甚至使用 f(1,d)，它进入无限循环，并重新启动内核。事实上，这种形式的任何功能，比如说

def f(n, d):
    return d.setdefault(n, f(n-1,d))

有同样的问题。当我尝试调试这个时，我看到 n 不断减小，通过值 1。我想我不明白这个方法的实现。我假设 setdefault 方法首先检查 key 是否在字典中并返回值，如果没有，则将默认值分配给 key 并返回默认值。我在这里缺少什么？（我使用 Python 3.9.1 和 Spyder 4.2.0）

4

1 回答 1

0

你仍然需要一个基本情况，否则没有什么可以阻止它计算，, fib(-1), fib(-2), fib(-99)...

def fib(n, d):
  return n if n < 2 else d.setdefault(n, fib(n-1, d) + fib(n-2, d))

print(fib(10, {0:0, 1:1}))

55

您遇到的问题setdefault是 python 是一种应用命令语言。这意味着在调用函数之前评估函数参数。在 的情况下，我们将在尝试查找之前进行setdefault评估。fib(n-1,d) + fib(n-2,d) nd

一个更好的接口可能是只有在需要设置默认值时才dict.setdefault(key, lambda: somevalue)执行 lambda 的地方。我们可以这样写——lazydefault

def lazydefault(d, key, lazyvalue):
  if key not in d:
    d[key] = lazyvalue()
  return d[key]

def fib(n, d):
  return lazydefault(d, n, lambda: fib(n-1, d) + fib(n-2, d))

print(fib(10, {0:0, 1:1}))

55
于 2021-01-06T01:03:40.603 回答