利用动态规则的思路，摒弃传统的递归做法，可以得到一种快速的求fibonacci第n个数的算法：
''' 求第n(从1开始)位fibonacci数 fibonacci数列前两位为0, 1. 后面每一位数字等于前两位数字之和 ''' def fibonacci( n ): if n <= 2: return n - 1 f = 0 g = 1 while n - 2 > 0: g = g + f f = g - f n -= 1 return g print( fibonacci( 100 ) ) ''' 与上述函数等价的递归写法 ''' def fib_iter( f, g, n ): if n <= 0: return g else: return fib_iter( g, f + g, n - 1 ) def fib( n ): if n <= 2: return n - 1 return fib_iter( 0, 1, n - 2 ) print( fib( 100 ) )两者原理一样, 但递归形式在计算fib(1000)的时候就超出python最大递归数量了, 所以推荐循环写法.
结果是218922995834555169026
转载于:https://www.cnblogs.com/tudas/p/dynamic-program-in-fibonacci.html
