/******************************************************************************
 * This program computes Fibonacci Numbers using recursion and memoization.
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.pureprogrammer.Utils;

public class Fibonacci2 {

    static List<Long> CACHED_FIBONACCI = Utils.listFromLongs(new long[]{1, 1});

    static long fibonacci(int n) {
        if (n < 2) {
            return 1;
        }
        if (n < CACHED_FIBONACCI.size()) {
            return CACHED_FIBONACCI.get(n);
        }
        final long RESULT = fibonacci(n - 1) + fibonacci(n - 2);
        CACHED_FIBONACCI.add(RESULT);
        return RESULT;
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci Sequence");
        for (int n = 1; n <= 80; ++n) {
            System.out.println(Utils.format("{0:d}: {1:d}", n, fibonacci(n)));
        }
    }
}