Memoization

Memoization is a technique for speeding up function calls by caching and reusing the output instead of recomputing for a given set of inputs. This technique offers a trade-off between memory and speed. The typical applications are for computationally expensive functions or for recursive functions, which branch out calling the recursive function many times with the same values, such as Fibonacci.

Let's use the latter to explore the effects of memoization. Fibonacci itself can be implemented recursively in the following manner:

    fun fib(k: Int): Long = when (k) { 
      0 -> 1 
      1 -> 1 
      else -> fib(k - 1) + fib(k - 2) 
    } 

Note that when we invoke fib(k), we need to invoke fib(k-1) and fib(k-2). However, fib(k-1) will itself invoke fib(k-2) and fib(k-3), and so on. The result is that we are making many duplicated calls with the same value. For example, for fib(5) we invoke fib(1) five separate times.

This diagram shows how the number...