不理解这个递归斐波那契实现

Question

这不是我的代码。我不明白第 3 行到底在做什么，逻辑操作。

cache = {}
def fiba(n):
     cache[n] = cache.get(n, 0) or (n <= 1 and 1 or fiba(n-1) + fiba(n-2))
     return cache[n]

n = 0
x = 0
while fiba(x) <= 4000000:
       if not fiba(x) % 2: n = n + fiba(x)
       x=x+1
print(n)

Answer 1

第 3 行 如果 n 为零，则条件语句的第一部分看起来返回零。第二部分是返回序列中的一个或下一个斐波那契数。所有这些都存储在缓存中（实际上只是一个数组）。

Answer 2

大致就是这样：

result = cache.get(n, 0)
if not result:  # i.e. if result == 0:
    if n <= 1:
        result = 1
    else:
        result = fiba(n - 1) + fiba(n - 2)
cache[n] = result

查看 docs on boolean operators 以更好地了解他们的工作。

Answer 3

在我看来，这似乎是一种通过缓存以前的计算来提高递归算法效率的尝试。在最简单的递归 Fibonacci 中，您只需

def fiba(n):
    return (n<=1 and 1) or fiba(n-1) + fiba(n-1)

的 shorthand

if(n<=1)
    return 1
else 
    return fiba(n-1)+fiba(n-2)

这将 return 1 代表 n=0，1 代表 n=1，然后下一个斐波那契数（计算为前 2 的总和）之后的所有 n。

如果我们仔细检查这段代码，我们会发现计算 fiba(4) 调用 fiba(3) 和 fiba(2)，后者又调用 fiba(2)、fiba(1)，分别为 fiba(1) 和 fiba(0)。请注意，我们多次调用 fiba(2) ，并且由于它本身是一个递归函数，因此这可能会变得昂贵，尤其是对于较大的数字，因为函数调用的数量在每个级别呈指数增长。因此，我们的想法是只计算每个 fiba(n) 一次，然后将其存储在内存中（cache），以便下次我们需要它时，我们可以简单地查找它而不是重新计算它。

你问的那一行是这项工作的大部分内容。我们将第 n 个斐波那契数存储在缓存的索引 [n] 处。条件从左到右计算：首先 cache.get(n,0) 查看我们是否已经计算出数字，如果是 return 则计算它。参数中的 0 表示如果键 n 不存在，缓存 returns 0 而不是 None。这并不是真正必要的，因为 0 或 None 都会导致评估 or 条件的另一侧。

简而言之，cache.get(n,0)检查该值是否已计算，如果没有，我们转到or的另一半。这将计算第 n 个数字，就像我们在没有缓存的函数中所做的那样，通过 fiba(0)=fiba(1)=1 的基本情况或通过对前两个值求和。

不理解这个递归斐波那契实现

Not understanding this recursive Fibonacci implementation

python

recursion

fibonacci

python-3.x