C++ メモとの再帰


再帰関数は非常に高価になる可能性があります。それらが純粋な関数(同じ引数で呼び出されたときに常に同じ値を返し、外部状態に依存したり変更しない関数)である場合、すでに計算された値を格納することによってメモリを犠牲にしてかなり高速にすることができます。

以下は、メモ処理によるフィボナッチシーケンスの実装です:

#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;
  }
}

このバージョンでは、呼び出し元は保存された値でマップを維持する必要があります。これにより、関数がリエントラントになり、呼び出し元が不要になった値を削除してメモリを節約できるという利点があります。それはカプセル化を破るという欠点があります。呼び出し側はマップに不正な値を設定して出力を変更することができます。