メモ化再帰関数とは 再帰関数内で、同じ引数の再帰関数を複数回呼び出すような実装では、その計算結果を保持しておくことで、複数回呼び出さないような実装にしようというのがメモ化再帰関数です
フィボナッチ数列とはイタリアの数学者レオナルド＝フィボナッチ（Leonardo Fibonacci）が名付けた数列です。
a[0] = 1, a[1] = 1
a[n + 2] = a[n] + a[n + 1]
（1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …）
このように前の2項を足してできあがる数列のことです。
普通の再帰でフィボナッチ数列を求める
以下のコードは普通の再帰でフィボナッチ数列の第n項を求めるものです。CalcFiboの引数が小さい場合はとくに問題はありませんが、1000程度の大きさの数になると待てど暮らせど処理が完了しません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Program { static void Main() { Console.WriteLine(CalcFibo(1)); Console.WriteLine(CalcFibo(2)); Console.WriteLine(CalcFibo(3)); Console.WriteLine(CalcFibo(1000)); // 時間がかかる・・・というかいつまでたっても終わらない } static int CalcFibo(int n) { if (n == 0) return 0; else if (n == 1) return 1; return CalcFibo(n - 1) + CalcFibo(n - 2); } } |
メモ化再帰でフィボナッチ数列を求める
上記のコードではCalcFiboを何度も呼び出しています。そこでメモ化再帰にします。ある引数が渡されたとき、その結果を保持しておくことで、また同じ引数で呼び出されたときすぐに値を返せるようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
public class Fibo { long[] memo = new long[1000 * 1000]; public Fibo() { } public long Calc(long n) { if (n == 0) return 0; else if (n == 1) return 1; if (memo[n] != 0) return memo[n]; memo[n] = (Calc(n - 1) + Calc(n - 2)); return memo[n]; } } class Program { static void Main() { Fibo fibo = new Fibo(); List<long> values = new List<long>(); for (int i = 1; i <= 10; i++) values.Add(fibo.Calc(i)); Console.WriteLine(String.Join(", ", values)); return; } } |
これだと大きな引数（ただし戻り値がlong型の範囲内に収まる程度のもの）であっても短時間で処理を返すことができます。
スタックオーバーフローの例外が・・・
ただそれでも再帰を繰り返すとスタックオーバーフローの例外が発生します。20,000くらいの値を渡すと例外が発生します（このくらいの値を渡すと計算結果はlong型の範囲を大きく超えてしまうので処理そのものに意味が無いと言えば意味が無い）。
では再帰を用いなければどうなるのでしょうか？
Calcメソッドが複数回呼び出された場合、最初から計算をしなくていいように計算結果とどこまで計算したかをフィールド変数に保存しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
public class Fibo2 { long[] memo = new long[1000 * 1000]; public Fibo2() { memo[0] = 0; memo[1] = 1; } // Calcメソッドが複数回呼び出された場合で、前回よりも大きな引数が渡されたときは // 途中から計算できるようにどこまで計算したか保存しておく int lastIndex = 0; public long Calc(long n) { if (n == 0) return 0; else if (n == 1) return 1; if (memo[n] > 0) return memo[n]; while (true) { if(memo[lastIndex + 2] == 0) memo[lastIndex + 2] = memo[lastIndex] + memo[lastIndex + 1]; if(lastIndex + 2 == n) return memo[lastIndex + 2]; lastIndex++; } } } class Program { static void Main() { List<long> values = new List<long>(); Fibo fibo = new Fibo(); for (int i = 1; i <= 10; i++) values.Add(fibo.Calc(i)); Console.WriteLine(String.Join(", ", values)); Console.WriteLine(); values.Clear(); Fibo2 fibo2 = new Fibo2(); for (int i = 1; i <= 10; i++) values.Add(fibo2.Calc(i)); // 同じものを異なる方法で計算しているだけなので // 当然のことながら出力は同じである Console.WriteLine(String.Join(", ", values)); Console.WriteLine(); // 桁あふれしているので戻り値に意味は無いが、少なくとも例外は発生しない Console.WriteLine(fibo2.Calc(1000 * 800)); } } |
