Memoization

Memoization is a useful technique to improve performance in some scenarios.

import org.funktionale.memoization.memoize

fun main(args: Array<String>) {

    lateinit var fib: (Long) -> Long // Declared ahead to be used inside recursively
    fib = { n: Long ->
        if (n < 2) n else fib(n - 1) + fib(n - 2)
    }
    lateinit var m: (Long) -> Long
    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 performance was made ~697 times faster using memoization.