python – 无法理解Fibonacci代码的递归和缓存

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 无法理解Fibonacci代码的递归和缓存，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2585字，纯文字阅读大概需要4分钟。

内容图文

我试图更好地理解递归和缓存,但我仍然取得了有趣的进展(有时候我有点慢).我在理解这段代码时遇到小问题：

# 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)

我在网上找到了这个代码,并试图评论每一行,以了解它实际上在做什么.我不明白这是一个递归,它确实循环代码,直到给出正确的结果,但我不知道它的调用本身.

我认为这是第一行：结果= FibonacciStorage._fib(number-1)FibonacciStorage._fib(number-2)但我很困惑,因为我的打印FibonacciStorage._storage行显示存储缓存增长和增长,但是它下面的一行是一个返回函数.我怀疑我不明白返回结果实际上是如何以某种方式再次触发递归.

我也不确定存储字典是如何让这个程序变得如此之快.我对fib序列的简单递归需要很长时间(即使我保存数据),但在这种情况下,如果你立即打印getFib(200).缓存怎么这么快？

总结一下,有两个问题：

1)如何实际触发递归？如果在每个循环上访问我的print语句？

2)缓存如何加速其他纤维序列？类结构或@static方法有所不同吗？例如,这似乎是即时的,而http://en.literateprograms.org/Fibonacci_numbers_(Python上的那些稍有延迟.

3)也许还有一点兴趣,一个fibnocci类型算法规模(分开并且并行运行)只是出于兴趣还是仅限于一个过程？

任何见解都会有所帮助.

解决方法:

(1)递归调用就在这一行：

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

你是对的,这是“实际的Fibonacci公式”,根据定义是递归的.

(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.而节省的只是随着您的增加而增加.

内容总结

以上是互联网集市为您收集整理的python – 无法理解Fibonacci代码的递归和缓存全部内容，希望文章能够帮你解决python – 无法理解Fibonacci代码的递归和缓存所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---