加快遞迴函數的計算

演算法中有一個簡單但是實用的技巧叫 memoization，可用於加快遞迴函數的計算，基本的想法就是把計算過的值儲存起來，並在呼叫前檢查是否已經計算過。

比如說我們要計算Fibonacci數列的值，公式為

F(0) = 0

F(1) = 1

F(n) = F(n-1), F(n-2)

用C++來實作並配合memoization的話程式如下

int fibonacci(int n)
{
    if (n<2)
        return n;
    static map<int,int> mymap;
    map<int,int>::iterator it;
    it = mymap.find(n);
    if (it==mymap.end())
    {
        int f = fibonacci(n-1) + fibonacci(n-2);
        mymap[n] = f;
        return f;
    }
    else
        return it->second;
} 

主要的概念在於使用 map 來儲存計算過的 f(n)。

上述的方法需要自己在程式中檢查傳入的參數是否有計算過，
然而人是懶惰的，在某些程式語言中可以將一個函數直接"升級"，
獲得memoization的能力。
比如說下面是ypcat提供的python的範例

def memoize(f, cache={}):
  def g(*args):
    key = tuple(args)
    if key not in cache:
      cache[key] = f(*args)
    return cache[key]
  return g

def fib(n):
  return n if n<2 else fib(n-1)+fib(n-2)

fib = memoize(fib)
print fib(300) 

比C++更方便的地方在於使用了一個函數 memoize 來包裝遞迴函數，執行的時候還可以把 fib() 直接替換為包裝過的函數。

Python, C#, Java, Lisp 等支援 first-class function 的語言都能達成以上功能，
那C++有沒有辦法自動memoization呢? 我目前還不確定。