import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone {
    private static Map<Integer, Integer> fibonacciNumbers = new HashMap<>();

    public static void main(String[] args) throws java.lang.Exception {
        int[] testCases = {0, 1, 2, 3, 4, 5, 10, 40};

        System.out.println("iterational algorighm");
        runTestCase(Ideone::getFibonacciNumber, testCases);

        System.out.println("recursive algorighm");
        runTestCase(Ideone::getFibonacciNumberRec, testCases);

        System.out.println("recursive algorighm with memoization");
        runTestCase(Ideone::getFibonacciNumberRec2, testCases);
    }

    public static int getFibonacciNumber(int n) {
        int previous1 = 1, previous2 = 1;
        int current = 1;
        for (int i = 1; i < n; i++) {
            current = previous1 + previous2;
            previous2 = previous1;
            previous1 = current;
        }

        return current;
    }

    public static int getFibonacciNumberRec(int n) {
        if (n < 2) return 1;
        return getFibonacciNumberRec(n - 1) + getFibonacciNumberRec(n - 2);
    }

    public static int getFibonacciNumberRec2(int n) {
        return fibonacciNumbers.computeIfAbsent(n,  i -> 
                (i < 2) ? 1 : getFibonacciNumberRec2(i - 1) + getFibonacciNumberRec2(i - 2));
    }

    private static void runTestCase(Function<Integer, Integer> function, int[] testCases) {
        long time = System.currentTimeMillis();
        for (int testCase : testCases) {
            System.out.println(function.apply(testCase));
        }
        System.out.println("Execution time - " + (System.currentTimeMillis() - time) + "ms");
    }
}