使用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中[[3,5],[2,3]]怎么转化为[['3','5'],['2','3']]？
从1分钟图上起笔递归至月线级别走势，这个工作量有多大吗？
python学习一定用pycharm吗？
python中[[3,5],[2,3]]怎么转化为[['3','5'],['2','3']]？
我想学Python，结果买了Python3.4.3的书，可以在Python3.6.4上用吗？
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？
什么是递归？
站在 2020 年回看，如何评价 Python 2 到 3 的升级？
从1分钟图上起笔递归至月线级别走势，这个工作量有多大吗？
前一个讨论
如何看待粥店挂“庆祝美日疫情”横幅 ？
下一个讨论
python如何将变量名转化为同名字符串？
相关的话题
Python 打包成 exe，太大了该怎么解决？为什么 macOS 在 /usr/bin/ 下会有 python3?
花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？
如何用python读取下面的csv文件？
将斐波那契数列从左到右、从上往下地依次填入一个n*n的矩阵中，当n≥3时，行列式是否一定为0？
是否无法写一段代码将这段代码自己打印出来？
什么是递归？
为什么 macOS 在 /usr/bin/ 下会有 python3?
将斐波那契数列从左到右、从上往下地依次填入一个n*n的矩阵中，当n≥3时，行列式是否一定为0？
站在 2020 年回看，如何评价 Python 2 到 3 的升级？
如何看待 Python 3.9 以上的版本不再支持 Windows 7？
Python 在大部分领域都能胜任，为什么很多企业转向了 Golang?
python中[[3,5],[2,3]]怎么转化为[['3','5'],['2','3']]？
Python中使用class()有什么优势 (PS：想知道实际应用中的优势)？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
Python 在大部分领域都能胜任，为什么很多企业转向了 Golang?
10/89 小数部分前 5 位可以构成斐波那契数列，这是一种巧合吗？
这样的广义斐波那契数列能得到如下的单调性结果吗？
你写过哪些真正生产可用的 Python 装饰器？
python中[[3,5],[2,3]]怎么转化为[['3','5'],['2','3']]？
如何用python读取下面的csv文件？
站在 2020 年回看，如何评价 Python 2 到 3 的升级？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
使用Python函数递归实现斐波那契数列时为什么运行速度很慢？
这样的广义斐波那契数列能得到如下的单调性结果吗？
站在 2020 年回看，如何评价 Python 2 到 3 的升级？
Python 打包成 exe，太大了该怎么解决？
Python 打包成 exe，太大了该怎么解决？
非计算机系学Python有什么建议？
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？