python - 无法理解斐波那契代码中的递归和缓存

Question

我正在尝试更好地理解递归和缓存，但我仍在取得有趣的进展(有时我有点慢)。我在理解这段代码时遇到了一些小问题:

# Fibonacci recursive with result storage

class FibonacciStorage:
    _storage = { 0:1, 1:1 }
    @staticmethod
    def _fib(number):
        try: # is this already calculated
            return FibonacciStorage._storage[number]   #searches dict, and if value exists then return it
        except KeyError:
            result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2)  #this is the actual Fibonacci Formula
            FibonacciStorage._storage[number] = result  #adds result to dictionary
            #print FibonacciStorage._storage #this shows the storage list growing with each iteration.
            return result
    @staticmethod
    def fib(number):  #first function, it has two asserts to basically make sure number is whole/positive and if its okay passes it to _fib(where the real work is done)
        # only do the assert statements once
        assert(isinstance(number,int)),"Needs a whole number" 
        assert(number>0),"Needs a positive whole number"
        return FibonacciStorage._fib(number)

# use a more readable name
getFib = FibonacciStorage.fib

print getFib(50)

我在网上找到了这段代码，并尝试对每一行进行注释以了解它的实际作用。我不明白这是一个递归，它确实循环遍历代码直到给出正确的结果，但我不明白它是如何调用自己的。

起初我以为是这一行:result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) 但我很困惑，因为我的 print FibonacciStorage._storage 行显示存储缓存在不断增长，但它下面的行是一个返回函数。我怀疑我不明白 return result 实际上是如何以某种方式再次触发递归的。

我也不确定存储字典是如何让这个程序运行得如此之快的。我对 fib 序列的简单递归需要很长时间(即使我保存了数据)，但在这种情况下，如果你立即执行 print getFib(200)。缓存如何让它如此之快？

总结一下，两个问题:

1) 递归实际上是如何被触发的？如果我的打印语句在每个循环中都被访问？

2) 缓存如何比其他 fib 序列加快速度？类结构或@staticmethod 是否有所作为？例如，这似乎是即时的，而 http://en.literateprograms.org/Fibonacci_numbers_(Python 上的那些) 有轻微的延迟。

3) 也许也是出于兴趣，斐波诺契类型的算法规模(拆分并并行运行)是否只是出于兴趣，或者它们是否仅限于一个过程？

任何见解都会有所帮助。

Answer 1

(1) 递归调用在这一行:

result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2)
//                   here ^                        and here ^

你是对的，这是“实际的斐波那契公式”，根据定义它是递归的。

(2) 缓存极大地加快了速度。不同之处在于持久对象 _storage ，这为您节省了大量的重复工作。惊人的。考虑:

                                 fib(4)
                               /        \
                          fib(3)   +     fib(2)
                         /    \          /     \
                    fib(2) + fib(1)   fib(1) + fib(0)
                    /    \
               fib(1) + fib(0)

这只是 fib(4) ，您已经可以看到冗余。通过简单地缓存 fib(3) 的整数值和 fib(4) ，您将减少 fib(5) 所需的计算次数从 7 到 1。节省的钱只会随着你的增加而增加。