谁能给我解释一下这个 "Dictionary" 版本的斐波那契数列是如何工作的？

Question

    known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]
    result = fibonacci(n-1) + fibonacci(n-2)
    known[n] = result
    return result

print(fibonacci(4))

那么fib的这本词典（背诵版）怎么样呢？序列有效？我认为 #whenever 我们调用一个新参数（以前没有调用过）需要一些时间来计算，就像递归版本一样。但它只是立即输出结果。这是否意味着所有斐波那契。结果存储在 python 程序本身中，所以它的计算速度非常快，因为我们使用了 dict。并称之为？

Answer 1

这是 memoization 的实现。字典将记录任何计算结果，以避免在使用相同参数调用函数时必须再次完成相同的工作。

如果没有记忆，该函数将如下所示：

def fibonacci(n):
    if n < 2:
        return n
    result = fibonacci(n-1) + fibonacci(n-2)
    return result

然后调用 fibonacci(5) 将导致对函数的这些调用：

fibonacci(5)
    fibonacci(4)
        fibonacci(3)
            fibonacci(2)
                fibonacci(1)
                   return 1
            fibonacci(1)
                return 1
        fibonacci(2)
            fibonacci(1)
                return 1
            fibonacci(0)
                return 0
    fibonacci(3)
        fibonacci(2)
            fibonacci(1)
               return 1
        fibonacci(1)
            return 1
    fibonacci(2)
        fibonacci(1)
            return 1
        fibonacci(0)
            return 0

请注意（例如）fibonacci(3) 是如何被调用两次的，并且对于这两次调用中的第二次调用，所有递归调用都会再次进行。总共 fibonacci(2) 被重新计算了四次。通过使用字典版本，递归树将不会做双重工作：

fibonacci(5)
    fibonacci(4)
        fibonacci(3)
            fibonacci(2)
                fibonacci(1)
                   return 1  # from dictionary
            fibonacci(1)
                return 1  # from dictionary
        fibonacci(2)
            return 1  # from dictionary
    fibonacci(3)
        return 2  # from dictionary

调用 fibonacci(5) 后字典将如下所示：

{
    0: 0,
    1: 1,
    2: 1,
    3: 2,
    4: 3,
    5: 5
}

因此，如果稍后调用 fibonacci(6)，递归树将不必那么深：

fibonacci(6)
    fibonacci(5)
       return 5  # from dictionary
    fibonacci(4)
       return 3  # from dictionary

...结果将被添加到字典中...等等

谁能给我解释一下这个 "Dictionary" 版本的斐波那契数列是如何工作的？

Can someone explain to me how this "Dictionary" version of Fibonacci sequence works?

python

dictionary

fibonacci