python 2.7 – 递归Fibonacci爆炸
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python 2.7 – 递归Fibonacci爆炸,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含974字,纯文字阅读大概需要2分钟。
内容图文
![python 2.7 – 递归Fibonacci爆炸](/upload/InfoBanner/zyjiaocheng/762/511a8e798c00432fb57493d7ace10478.jpg)
我有两个函数fib1和fib2来计算Fibonacci.
def fib1(n):
if n < 2:
return 1
else:
return fib1(n-1) + fib1(n-2)
def fib2(n):
def fib2h(s, c, n):
if n < 1:
return s
else:
return fib2h(c, s + c, n-1)
return fib2h(1, 1, n)
fib2工作正常,直到它超过递归限制.如果理解正确,Python不会针对尾递归进行优化.我很好.
让我的是,即使n值非常小,fib1也开始减速停止.为什么会这样?为什么它在缓慢之前没有达到递归限制?
解决方法:
基本上,你通过计算fib1以获得相同的n值来浪费大量时间.您可以轻松地记住这样的功能
def fib1(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
memo[n] = 1
else:
memo[n] = fib1(n-1) + fib1(n-2)
return memo[n]
您会注意到我使用空dict作为默认参数.这通常是一个坏主意,因为相同的dict被用作每个函数调用的默认值.
在这里,我利用它来记住我计算的每个结果
您还可以使用0和1来填充备忘录,以避免需要n< 2测试
def fib1(n, memo={0: 1, 1: 1}):
if n in memo:
return memo[n]
else:
memo[n] = fib1(n-1) + fib1(n-2)
return memo[n]
哪个成了
def fib1(n, memo={0: 1, 1: 1}):
return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))
内容总结
以上是互联网集市为您收集整理的python 2.7 – 递归Fibonacci爆炸全部内容,希望文章能够帮你解决python 2.7 – 递归Fibonacci爆炸所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。