带有 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;
  }
}

对于此版本，调用者需要使用存储的值维护映射。这样做的好处是该函数现在可以重入，并且调用者可以删除不再需要的值，从而节省内存。它的缺点是它破坏了封装; 调用者可以通过使用不正确的值填充映射来更改输出。