import java.util.Date

fun <I, U> memoize(f: (I) -> U): (I) -> U {
    val memo = hashMapOf<I, U>()
    return { x: I ->
        var r = memo[x]
        if (r == null) {
            r = f(x)
            memo[x] = r
        }
        r!!
    }
}

fun fibonacci(x: Int): Int {
    if (x <= 2) {
        return 1
    } 
    return fibonacci(x - 1) + fibonacci(x - 2)
}

val memFibonacci = memoize(::fibonacci)

for (i in 1..2) {
    val start = Date()
    val f37 = memFibonacci(37)
    val milliseconds = Date().time - start.time

    println("$i: f37 is $f37")
    println("$i: milliseconds is $milliseconds")
}
// prints:
// 1: f37 is 24157817
// 1: milliseconds is 71
// 2: f37 is 24157817
// 2: milliseconds is 0

val start = Date()
val f38 = memFibonacci(38)
val milliseconds = Date().time - start.time

println("f38 is $f38")
println("milliseconds is $milliseconds")
// f38 is 39088169
// milliseconds is 114