斐波那契数列的高效 Pythonic 生成器
我在尝试获得该序列的最短 Pythonic 生成时发现了这个问题（后来意识到我在Python Enhancement Proposal中看到过类似的问题），并且我没有注意到其他人提出了我的具体解决方案（尽管最佳答案很接近，但仍然不那么优雅），所以在这里，带有描述第一次迭代的评论，因为我认为这可能有助于读者理解：
def fib():
a, b = 0, 1
while True: # First iteration:
yield a # yield 0 to start with and then
a, b = b, a + b # a will now be 1, and b will also be 1, (0 + 1)
和用法：
for index, fibonacci_number in zip(range(10), fib()):
print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))
印刷：
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
（出于归因的目的，我最近注意到Python 文档中关于模块的类似实现a，即使使用变量和b，我现在记得在写这个答案之前已经看到过。但我认为这个答案展示了更好地使用语言。）
递归定义的实现
整数序列在线百科全书将斐波那契数列递归定义为
F(n) = F(n-1) + F(n-2) 其中 F(0) = 0 且 F(1) = 1
在 Python 中简洁地递归定义 this 可以如下完成：
def rec_fib(n):
'''inefficient recursive function as defined, returns Fibonacci number'''
if n > 1:
return rec_fib(n-1) + rec_fib(n-2)
return n
但是这种数学定义的精确表示对于远大于 30 的数字来说是非常低效的，因为每个被计算的数字还必须计算它下面的每个数字。您可以使用以下方法演示它有多慢：
for i in range(40):
print(i, rec_fib(i))
记忆递归提高效率
它可以被记忆以提高速度（这个例子利用了这样一个事实，即每次调用函数时默认关键字参数都是同一个对象，但通常你不会因为这个原因而使用可变的默认参数）：
def mem_fib(n, _cache={}):
'''efficiently memoized recursive function, returns a Fibonacci number'''
if n in _cache:
return _cache[n]
elif n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
你会发现记忆的版本要快得多，并且会在你想起来喝咖啡之前迅速超过你的最大递归深度。通过执行以下操作，您可以直观地看到它的速度有多快：
for i in range(40):
print(i, mem_fib(i))
（看起来我们可以做下面的事情，但它实际上并没有让我们利用缓存，因为它在调用 setdefault 之前调用了自己。）
def mem_fib(n, _cache={}):
'''don't do this'''
if n > 1:
return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
return n
递归定义的生成器：
由于我一直在学习 Haskell，我在 Haskell 中遇到了这个实现：
fib@(0:tfib) = 0:1: zipWith (+) fib tfib
我认为目前在 Python 中最接近这一点的是：
from itertools import tee
def fib():
yield 0
yield 1
# tee required, else with two fib()'s algorithm becomes quadratic
f, tf = tee(fib())
next(tf)
for a, b in zip(f, tf):
yield a + b
这证明了这一点：
[f for _, f in zip(range(999), fib())]
但是，它只能达到递归限制。通常是 1000，而 Haskell 版本可以达到数百万，尽管它使用了我笔记本电脑的全部 8 GB 内存来做到这一点：
> length $ take 100000000 fib
100000000
使用迭代器获取第 n 个斐波那契数
一位评论者问：
基于迭代器的 Fib() 函数的问题：如果你想获得第 n 个，例如第 10 个 fib 编号怎么办？
itertools 文档对此有一个秘诀：
from itertools import islice
def nth(iterable, n, default=None):
"Returns the nth item or a default value"
return next(islice(iterable, n, None), default)
现在：
>>> nth(fib(), 10)
55
