使用快取加速遞迴函式

大家都知道 Fibonacci 序列 吧， 公式很簡單

f(n) = f(n-1)+f(n-2),  f(0) = 0,  f(1) = 1

Fibonacci 的公式是遞迴的， 因為要計算 f(n) 需要上次及上上次計算的結果。 直接套定義就有下面的函式 (in Python)

def fib(n):
   if n in (0, 1):
      return n
   return fib(n-1) + fib(n-2)

實際測試，會發現上面函式的執行效率非常差， 比方說我們要計算 f(5)，套定義，要先計算 f(3) 跟 f(4)， 可是要計算 f(4) 又要先知道 f(3) 跟 f(2)， 也就是說實際上 f(3) 算了兩次，依此類推 f(2) 計算了三次， 如果 n 很大的話，計算 f(n) 就會重覆很多不必要的計算， 要解決這個問題不難，在函式中加入一個快取來記錄之前算過的值就可以了

cache_v2 = {}
def fib_v2(n):
   if n in (0, 1):
      return n
   if n in cache_v2:
      return cache_v2[n]
   else:
      cache_v2[n] = value = fib_v2(n-1) + fib_v2(n-2)
      return value

上面程式碼中紅色部分是為了要使用快取所增加的程式碼，下面是另一種版本，

cache_v3 = {}
def fib_v3(n):
   if n in (0, 1):
      return n
   try:
      return cache_v3[n]
   except KeyError:
      cache_v3[n] = value = fib_v3(n-1) + fib_v3(n-2)
      return value

版本 v3 的好處是可以加入其它偵錯的功能， 比方說除了 catch KeyError 還可以再增加程式碼 catch TypeError， 根據我測試的結果，版本 v3 會比版本 v2 慢一點點， 不過這一點點時間，是幾乎可以忽略的，所以可以安心的使用版本 v3 的寫法。

不過版本 v2 和 v3 也不是沒有缺點，跟原來的版本 fib() 相比， 程式碼比較不直接，而且需要額外的空間，這個空間需要在函式可以存取的地方宣告。 還有，假設我們有很多類似 fib() 的函式需要利用快取來加速， 難到我們需要一個一個修改程式碼嗎？ 這對於擁有 laziness, impatience, and hubris 三項美德的程式設計師是無法忍受的。 比較好的做法是不要動到 fib() 的實作內容，而是把 fib() 當作一物件， 再另外寫一個函式或類別來處理 fib()， 利用 Python 2.4 引入的語法 Decorator 可以達到這個目的。我將在之後的部落格介紹這個語法，請拭目以待 XD