如何生成斐波那契數列

斐波那契（Fibonacci）數列是一個非常簡單的遞歸數列，除第一個和第二個數外，任意一個數都可由前兩個數相加得到。用計算機程序輸出斐波那契數列的前 N 個數是一個非常簡單的問題，許多初學者都可以輕易寫出如下函數：

清單 1. 簡單輸出斐波那契數列前 N 個數

 def fab(max):   n, a, b = 0, 0, 1   while n < max:     print b     a, b = b, a + b     n = n + 1

執行 fab(5)，我們可以得到如下輸出：

 >>> fab(5)
 1
 1
 2
 3
 5

結果沒有問題，但有經驗的開發者會指出，直接在 fab 函數中用 print 打印數字會導致該函數可復用性較差，因為 fab 函數返回 None，其他函數無法獲得該函數生成的數列。

要提高 fab 函數的可復用性，最好不要直接打印出數列，而是返回一個 List。以下是 fab 函數改寫后的第二個版本：

清單 2. 輸出斐波那契數列前 N 個數第二版

 def fab(max):   n, a, b = 0, 0, 1   L = []   while n < max:     L.append(b)     a, b = b, a + b     n = n + 1   return L

可以使用如下方式打印出 fab 函數返回的 List：

 >>> for n in fab(5):
 ...     print n
 ...
 1
 1
 2
 3
 5

改寫后的 fab 函數通過返回 List 能滿足復用性的要求，但是更有經驗的開發者會指出，該函數在運行中占用的內存會隨著參數 max 的增大而增大，如果要控制內存占用，最好不要用 List來保存中間結果，而是通過 iterable 對象來迭代。例如，在 Python2.x 中，代碼：

清單 3. 通過 iterable 對象來迭代

 for i in range(1000): pass會導致生成一個 1000 個元素的 List，而代碼：

 for i in xrange(1000): pass則不會生成一個 1000 個元素的 List，而是在每次迭代中返回下一個數值，內存空間占用很小。因為 xrange 不返回 List，而是返回一個 iterable 對象。

利用 iterable 我們可以把 fab 函數改寫為一個支持 iterable 的 class，以下是第三個版本的 Fab：

清單 4. 第三個版本

class Fab(object):   def __init__(self, max):     self.max = max     self.n, self.a, self.b = 0, 0, 1   def __iter__(self):     return self   def next(self):     if self.n < self.max:       r = self.b       self.a, self.b = self.b, self.a + self.b       self.n = self.n + 1       return r     raise StopIteration()

Fab 類通過 next() 不斷返回數列的下一個數，內存占用始終為常數：

 >>> for n in Fab(5):