【アルゴリズム】メモ化再帰関数を用いた高速化

はじめに

本記事ではフィボナッチ数列を題材にして、メモ化再帰関数を用いた高速化についてまとめたいと思います。

再帰関数ってなに？って方は再帰関数についての記事をご覧ください。

メモ化再帰関数とは

再帰関数内で、同じ引数の再帰関数を複数回呼び出すような実装では、その計算結果を保持しておくことで、複数回呼び出さないような実装にしようというのがメモ化再帰関数です。計算結果を配列に代入するという処理を加えるだけなので、非常に簡単にできる高速化になります。

フィボナッチ数列とは

フィボナッチ数列とは、以下のように定義される数列です。

F_0=0, F_1=1\\
F_N = F_{N-1}+F_{N-2}(N=2,3,...)

再帰関数によるフィボナッチ数列の実装

通常の再帰関数で実装すると以下のようになります。

# include <iostream>
# include <vector>
using namespace std;

vector<int> cnt(11);

int calc_fibo(int N){
  cnt[N]++;

  if (N == 0) return 0;
  else if (N == 1) return 1;

  return calc_fibo(N - 1) + calc_fibo(N - 2);
}

int main(){
  cout << calc_fibo(10) << endl; // 55
  int total = 0;
  for (int i = 0; i < cnt.size(); ++i) {
    cout << "calc_fibo(" << i << "):" << cnt[i] << "回" << endl;
    total += cnt[i];
  } 
  cout << "total:" << total << "回" << endl;
}

上記のコードの出力は以下のようになります。

55
calc_fibo(0):34回
calc_fibo(1):55回
calc_fibo(2):34回
calc_fibo(3):21回
calc_fibo(4):13回
calc_fibo(5):8回
calc_fibo(6):5回
calc_fibo(7):3回
calc_fibo(8):2回
calc_fibo(9):1回
calc_fibo(10):1回
total:177回

出力を見ると、同じ関数が何度も呼ばれていて、計算量やメモリの観点から効率が悪いことがわかります。そこで、一度計算した値を保持しておくことで、無駄に関数を呼び出さなくて良くなります。

メモ化再帰関数による高速化

メモ化再帰関数で実装すると以下のようになります。memo配列の値はありえない数値で初期化しておきます。

# include <iostream>
# include <vector>
using namespace std;

vector<int> cnt(11);
vector<int> memo(11, -1);

int calc_fibo(int N){
  cnt[N]++;

  if (N == 0) return 0;
  else if (N == 1) return 1;

  if (memo[N] != -1) return memo[N];

  return memo[N] = calc_fibo(N - 1) + calc_fibo(N - 2);
}

int main(){
  cout << calc_fibo(10) << endl; // 55
  int total = 0;
  for (int i = 0; i < cnt.size(); ++i) {
    cout << "calc_fibo(" << i << "):" << cnt[i] << "回" << endl;
    total += cnt[i];
  } 
  cout << "total:" << total << "回" << endl;
}

上記のコードの出力は以下のようになります。

55
calc_fibo(0):1回
calc_fibo(1):2回
calc_fibo(2):2回
calc_fibo(3):2回
calc_fibo(4):2回
calc_fibo(5):2回
calc_fibo(6):2回
calc_fibo(7):2回
calc_fibo(8):2回
calc_fibo(9):1回
calc_fibo(10):1回
total:19回

計算結果をmemo配列に保持しておくことで、関数の呼び出し回数が177回から19回に激減しました！

最後に

本記事ではメモ化再帰関数についてまとめました。次は動的計画法についての記事を書きたいと思ってます！（メモ化再帰関数もそれに似てますが）