斐波那契級數(shù)真是計算機(jī)教學(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)用生成器葫辐，生成器運(yùn)行到 yield搜锰，然后就被凍結(jié)起來，同時保存狀態(tài)耿战；下一次調(diào)用蛋叼，會從生成器被凍結(jié)的狀態(tài)繼續(xù)運(yùn)行。生成器依賴于惰性計算（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ù)松却，可以對以上無窮生成器進(jìn)行操作，在簡化寫法的同時溅话，充分發(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券勺。
