メモ化再帰

フィボナッチとかくらいしか、再帰を使ったことないのですが
動的計画法（DP）を勉強中にメモ化再帰、という単語が登場し、こりゃあスゴイ！と思ったのでメモ。

概要

各数字における答えをメモしておく。
再帰関数は同じ値に対する計算を何度も行うので、処理が遅くなってしまう。
これを防ぐために、再帰で関数が呼ばれた際に、既にメモしていた答えがある場合は、計算せずにそれを返す、というやり方。

コード

import java.util.*;

public class RecFibTest {
    public static void main(String[] args) {
        long[] memo = new long[50];
        Arrays.fill(memo, -1);
        for(int i=0; i<50; i++) {
            System.out.println("i : " +  i + " fib : " + fibo(i, memo));
        }
    }

    public static long fibo(int i, long[] memo) {
        if(i == 0) {
            return 0;
        } else if(i == 1) {
            return 1;
        }

        if(memo[i] != -1) {
            return memo[i];
        }

        memo[i] = (fibo(i-1, memo) + fibo(i-2, memo));
        return memo[i];
    }
}

参考

qiita.com