斐波那契級數(shù)真是計算機教學(xué)的萬用示例。f(n) = f(n-1) + f(n-2) 這種實現(xiàn)方案可以示范遞歸函數(shù)；而在算法課程中，它又成了指數(shù)級別復(fù)雜度算法的反面典型；由于值增長得很快，接下來就可以講授如何設(shè)計一個新的數(shù)據(jù)類型來表示這些迅速增長的數(shù)值了……

今天，我們拿它來講講 Python 語言的一些特性，特別是對函數(shù)式編程（functional programming）的支持。

生成器與惰性計算

這其實是 Python Cookbook 第二版中的一個例子：需要一個無界的生成器，它能一次一項地生成斐波那契數(shù)的整個序列。

Python 的生成器（generator）可以完美地解決這類問題。每次調(diào)用生成器，生成器運行到 yield，然后就被凍結(jié)起來，同時保存狀態(tài)；下一次調(diào)用，會從生成器被凍結(jié)的狀態(tài)繼續(xù)運行。生成器依賴于惰性計算（lazy evaluation），即只有在請求到來時，一項數(shù)據(jù)才會被計算出來。對于生成類的問題，尤其是無窮生成問題，生成器的實現(xiàn)是再合適不過了：

def fib():
    x, y = 0, 1
    while True:
        yield x
        x, y = y, x + y

可以用 itertools.islice 方法獲得級數(shù)的前 n 項：

In [2]: from itertools import *

In [3]: list(islice(fib(), 10))
Out[3]: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Python 對函數(shù)式編程的支持：itertools

以生成器的形式生成斐波那契級數(shù)有什么好處呢？Python 對函數(shù)式編程有較好的支持，itertools 中提供了一系列函數(shù)，可以對以上無窮生成器進行操作，在簡化寫法的同時，充分發(fā)揮惰性計算的優(yōu)勢。

如果要得到所有1000以下的斐波那契數(shù)，可以使用 takewhile：

In [4]: list(takewhile(lambda x: x < 1000, fib()))
Out[4]: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]

第20項（從第0項開始計）：

In [5]: next(islice(fib(), 20, None))
Out[5]: 6765

第一個大于100000的項：

In [6]: next(filter(lambda x: x > 100000, fib()))
Out[6]: 121393

可以看到，代碼短小精悍，非常 functional，生成器 fib() 得到了最大程度的復(fù)用。

更多信息，可以閱讀 Python 官方文檔10.1. itertools
— Functions creating iterators for efficient looping。