使用Python函数递归实现斐波那契数列时为什么运行速度很慢？ 第1页
1
li-xiang-1-48 网友的相关建议:
本人在用python计算同分异构体数量的时候遇到了类似问题。原因是，递归逻辑导致总是重复计算前面已经算过的内容。
例如，计算Fib(5)的时候，需要先算出Fib(3)和Fib(4)，但算出Fib(3)后，在计算Fib(4)=Fib(2)+Fib(3)的时候，又计算了一次Fib(3).
（图片来自使用缓存方式优化递归函数与lru_cache - sfencs - 博客园）
这样下去，到计算Fib(100)的时候，就至少需要计算两次Fib(98)，而计算Fib(98)又至少需要计算两次Fib(96)，时间复杂度为指数级，所以程序短时间内无法完成。
有一个简单的解决方案：使用lru_cache缓存装饰器，缓存一些中间结果：
from functools import lru_cache @lru_cache(maxsize=1024) # 缓存斐波那契函数已经计算出的结果，最多占用1024字节内存 def fibn(n): if n == 0: return 1 elif n == 1: return 1 else: return fibn(n-1) + fibn(n-2) print(fibn(100)) # 求第100项的值，可瞬间计算出来 1
相关话题
非计算机系学Python有什么建议？花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
如何用python读取下面的csv文件？
这样的广义斐波那契数列能得到如下的单调性结果吗？
什么是递归？
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
Python函数中*和**的内涵究竟是什么呢？
你写过哪些真正生产可用的 Python 装饰器？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
前一个讨论
如何看待粥店挂“庆祝美日疫情”横幅 ？
下一个讨论
python如何将变量名转化为同名字符串？
相关的话题
将斐波那契数列从左到右、从上往下地依次填入一个n*n的矩阵中，当n≥3时，行列式是否一定为0？从1分钟图上起笔递归至月线级别走势，这个工作量有多大吗？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
什么是递归？
Python函数中*和**的内涵究竟是什么呢？
Python中使用class()有什么优势 (PS：想知道实际应用中的优势)？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
Python 打包成 exe，太大了该怎么解决？
有那位大神使用过tensorflow-textsum来做文本摘要么？求指教？
Python 在大部分领域都能胜任，为什么很多企业转向了 Golang?
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
非计算机系学Python有什么建议？
10/89 小数部分前 5 位可以构成斐波那契数列，这是一种巧合吗？
如何看待 Python 3.9 以上的版本不再支持 Windows 7？
如何看待 Python 3.9 以上的版本不再支持 Windows 7？
花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
Python 在大部分领域都能胜任，为什么很多企业转向了 Golang?
这样的广义斐波那契数列能得到如下的单调性结果吗？
花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
python学习一定用pycharm吗？
什么是递归？
你写过哪些真正生产可用的 Python 装饰器？
Python3.10的新特性match关键字为什么不会和当前作用域的变量名称match冲突？
Python 打包成 exe，太大了该怎么解决？
从1分钟图上起笔递归至月线级别走势，这个工作量有多大吗？
如何用python读取下面的csv文件？
python学习一定用pycharm吗？
如何看待 Python 3.9 以上的版本不再支持 Windows 7？
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？
python学习一定用pycharm吗？