import java.util.*;
import java.util.function.*;

<I, U> Function<I, U> Memoize(
    Function<I, U> fun) {
    var memo = new HashMap<I, U>();

    return x -> {
        if (memo.containsKey(x)) {
            return memo.get(x);
        }
        U r = fun.apply(x);
        memo.put(x, r);
        return r;
    };
}

int Fibonacci(int x) {
    return x <= 2 ? 1 :
        Fibonacci(x - 1) + Fibonacci(x - 2);
}

var memFibonacci = Memoize(
    (Integer x) -> Fibonacci(x));

for (var i = 1; i <= 2; i++) {
    var start = new Date();
    var f37 = memFibonacci.apply(37);
    var milliseconds = (new Date()).getTime() - start.getTime();

    System.out.printf("%d: f37 is %d\n", i, f37);
    System.out.printf("%d: milliseconds is %d\n", i, milliseconds);
}
// prints:
// 1: f37 is 24157817
// 1: milliseconds is 46
// 2: f37 is 24157817
// 2: milliseconds is 0

var start = new Date();
var f38 = memFibonacci.apply(38);
var milliseconds = (new Date()).getTime() - start.getTime();

System.out.printf("f38 is %d\n", f38);
System.out.printf("milliseconds is %d", milliseconds);
//f38 is 39088169
//milliseconds is 74