python实现斐波那契数列的方法

普通的代码

def fibonacci(n):
    assert(n>=0), 'n must be >= 0'
    return n if n in (0, 1) else fibonacci(n-1) + fibonacci(n-2)

if __name__ == '__main__':
    from timeit import Timer
    t = Timer('fibonacci(8)', 'from __main__ import fibonacci')
    print('value: {}\n'.format(fibonacci(8)))
    print('time: {}'.format(t.timeit()))

在我的机子上要8s的时间:

memoization方法的代码

known = {0:0, 1:1}
def fibonacci(n):
    assert(n>=0), 'n must be >= 0'
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res 
    return res
if __name__ == '__main__':
    from timeit import Timer
    t = Timer('fibonacci(999)', 'from __main__ import fibonacci')
    print('value: {}\n'.format(fibonacci(999)))
    print('time: {}'.format(t.timeit()))

只需要0.167s:

结论

使用记忆来存储已求过的值,可以提高效率。在人类文明的进程中也一样,知识如果能保留起来,比如我这篇博客,那么以后再调用的话可以快很多,站在巨人的肩膀上。

遗留问题

但是如果递归数大于等于1000,那么就会报错,报错的原因是什么呢?以后有机会再深入了解。详见图:

经吉林大神指导:

python的default递归深度是1000,所以当递归深度大于999的时候就会报错,可以用这样的代码调整一下。

import sys
sys.setrecursionlimit(2000) //设置递归最大层数

这只是缓兵之计,好的方法还是要优化自身代码

2 thoughts on “python实现斐波那契数列的方法”

  1. python的递归深度是1000,所以当递归深度大于999的时候就会报错,可以用这样的代码调整一下。

    import sys
    sys.setrecursionlimit(2000)

    这只是缓兵之计,好的方法还是要优化自身代码

Comments are closed.