C++
C ++での再帰

Fibonnaciシーケンスを解くためのテール再帰とFibonnaciスタイルの再帰の使用

再帰を使ってFibonnaciシーケンスのN番目の項を求める簡単で最も明白な方法は、これです

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

しかし、このアルゴリズムは、より高い用語のためにスケールしない：どんどん大きくするためにn 、機能の数は、あなたが指数関数的に増加させる必要があることを呼び出します。これは簡単なテール再帰と置き換えることができます。

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

関数呼び出しのたびに、Fibonnaciシーケンスの次の項がすぐに計算されるため、関数呼び出しの数はn直線的に比例します。

メモとの再帰

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

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

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

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