fib在python中什么意思,fib()相关的一些事

所有代码均来自于Python 2.7 版本

相信对于所有有过编程经历的童鞋而言，递归都是一个再熟悉不过的概念。而在初学递归的时候，相信斐波那契数列都是一个重要的例子(另一个则是汉诺塔(Hanoi))。今天就利用求第n项斐波那契数列作为一个例子，来简单说一下我对几个概念的理解。

递归

话不多说，直接上代码就好

def fib(n):

if n> fib(1000)

...

RuntimeError: maximum recursion depth exceeded

显然，1000已经超出了Python的最大递归深度。那么，有没有什么方法对递归进行优化呢？

迭代

一般认为，所有的递归都可以写成迭代，区别在于编程时间的花费以及代码量、可读性方面的问题。

简单思考一下，写出下面代码应该不难。

def fib(n):

a, b = 1, 1

if n>> fib(1000)

...

RuntimeError: maximum recursion depth exceeded

意外发现，竟然和普通递归抛出一样的异常。这是什么原因呢？简单搜索一下，悲剧的得知，Python在语言层面，并不支持尾递归优化且对递归次数有限制。

Yield

那么，就没有办法对于大规模输入使用递归写法了吗？

答案是有的。想想看，递归之所以无法工作，根本原因在于内存的大量占用和递归深度超限。所以说，只要削减递归占用的内存，就可以使用递归写法，享受递归带来的方便了。

yield关键字恰好是具有这种功能的解决方案。它产生一个生成器，它具有惰性求值的属性。对内存的占用是常数级别的，不随输入规模增大而增大。

def fib(count, tmp=1, next_step=1):

if count < 2:

yield tmp

else:

yield fib(count-1, next_step, next_step+tmp)

调用的时候

b = fib(1000)

for _ in xrange(1000):

b = b.next()

print b

效率

最后，利用运行时间，来比较一下迭代算法和尾递归的效率。

首先，写一个计算运行时间的装饰器。

def timeit(fun):

def wrapped(*args, **kwargs):

import time

t1 = time.time()

execFun = fun(*args, **kwargs)

//为了体现差别，让函数执行1000次

for _ in xrange(1000):

fun(*args, **kwargs)

t2 = time.time()

print t2 - t1

return execFun

return wrapped

def fib1_helper(count, tmp=1, next_step=1):

if count < 2:

yield tmp

else:

yield fib1_helper(count-1, next_step, next_step+tmp)

@timeit

def fib1(n):

b = fib1_helper(n)

for _ in xrange(n):

b = b.next()

@timeit

def fib2(n):

a, b = 1, 1

if n>> fib1(1000)

>>> fib2(1000)

//以下执行结果因执行环境不同可能存在差异

0.641000032425

0.0920000076294

可以看出，相比递归，迭代在执行时间上还是有着不小的优势。但是尾递归+yield的组合实现了递归写法，在某些问题上降低了编程时间的消耗，在某些场景下可以考虑作为一种新的思路。