帶有 memoization 的遞迴

遞迴函式可能會非常昂貴。如果它們是純函式（當使用相同的引數呼叫時總是返回相同的值，並且既不依賴也不修改外部狀態），通過儲存已經計算的值，可以以犧牲記憶體為代價使它們更快。

以下是具有 memoization 的 Fibonacci 序列的實現：

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

請注意，儘管使用簡單的遞迴公式，但在第一次呼叫時此函式為$ O(n)$。在具有相同值的後續呼叫中，它當然是$ O(1)$。

但請注意，此實現不可重入。此外，它不允許擺脫儲存的值。另一種實現方式是允許將地圖作為附加引數傳遞：

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

對於此版本，呼叫者需要使用儲存的值維護對映。這樣做的好處是該函式現在可以重入，並且呼叫者可以刪除不再需要的值，從而節省記憶體。它的缺點是它破壞了封裝; 呼叫者可以通過使用不正確的值填充對映來更改輸出。