// Fib_Memoized.java

public class Fib_Memoized {
    // remember results of past calculations
    private static long[] results;

    // recursive fibonacci sequence w/ memoization
    public static long recursive_fib(int number) {
        // if we've already calculated this, use the saved result
        if (results[number] != 0) {
            return results[number];
        }

        // the base case of 0 or 1
        if (number <= 2) {
            results[number] = 1;
            return 1;
        } else {
            // figure it out, then save it in the array
            long answer = recursive_fib(number - 1) + recursive_fib(number - 2);
            results[number] = answer;
            return answer;
        }
    }

    public static void main(String args[]) {
        // setup the space for saved results
        results = new long[1000];

        for (int i = 1; i <= 100; i++) {
            System.out.println(i + "th fibonacci = " + recursive_fib(i));
        }
    }
}