Memoization

Memoization is a useful technique that let us improve performance in some scenarios

import org.funktionale.memoization.memoize

fun main(args: Array<String>) {

    var fib: (Long) -> Long = { it } //Declared ahead to be used inside recursively
    fib = { n: Long ->
        if (n < 2) n else fib(n - 1) + fib(n - 2)
    }
    var m: (Long) -> Long = { it }
    m = { n: Long ->
        if (n < 2) n else m(n - 1) + m(n - 2)
    }.memoize()

    println(timeElapsed { fib(40) }) //2788

    println(timeElapsed { m(40) })  //4
}

fun timeElapsed(body: () -> Unit): Long {
    val start = System.currentTimeMillis()
    body()
    val end = System.currentTimeMillis()
    return end - start
}

In this case the difference in performance was 697~ times