python 2.7 – 递归Fibonacci爆炸

概述我有两个函数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 我有两个函数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,1: 1}):    return memo.setdefault(n,memo.get(n) or fib1(n-1) + fib1(n-2))

总结

以上是内存溢出为你收集整理的python 2.7 – 递归Fibonacci爆炸全部内容，希望文章能够帮你解决python 2.7 – 递归Fibonacci爆炸所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。