public class FibonacciMemo {

    // Penghitung panggilan untuk naive dan memo versi.
    static long panggilNaive = 0;
    static long panggilMemo = 0;

    // Versi naive: menghitung ulang subpersoalan yang sama berkali-kali.
    static long fibNaive(int n) {
        panggilNaive++;
        if (n <= 1) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Versi top-down dengan memo: hasil subpersoalan disimpan di array memo.
    static long fibMemo(int n, long[] memo) {
        panggilMemo++;
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 30;

        System.out.println("=== Naive rekursif vs memoization, fib(" + n + ") ===");
        System.out.println("fibNaive(" + n + ") = " + fibNaive(n));
        System.out.println("Jumlah panggilan naive : " + panggilNaive);
        System.out.println("fibMemo(" + n + ")  = " + fibMemo(n, new long[n + 1]));
        System.out.println("Jumlah panggilan memo  : " + panggilMemo);
        System.out.println();
        System.out.println("Perbandingan panggilan : " + panggilNaive + " vs " + panggilMemo
                + " (sekitar " + (panggilNaive / panggilMemo) + "x lebih banyak)");
    }
}