Speeding Recurrence Calculation by Memorization

The Fibonacci sequence is represented by the following incremental formula.

$$ F_{0} = 0\\\
F_{1} = 1\\\
F_{N} = F_{N - 1} + F_{N - 2} \bigl(N = 2, 3, …\bigr) $$

The algorithm using recursion is widely known to calculate the Nth item of Fibonacci sequence. Here is an implementation of Fibonacci number calculation by recursion.

fun main(args: Array<String>) {
  fun fib(n: Long): Long =
    when (n) {
      0L -> 0L
      1L -> 1L
      else -> fib(n - 1L) + fib(n - 2L)
    }

  check(fib(0L) == 0L)
  check(fib(1L) == 1L)
  check(fib(2L) == 1L)
  check(fib(50L) == 12586269025L)
}

It is also widely known that the implementation has a big problem. Namely, the computation cost is $O\Bigl(\bigl(\frac{1+\sqrt{5})}{2}\bigr)^N\Bigr)$ and increases exponentially. For example, if $ N = 50 $, it is recursed 20.3 billion times and it’ll take very very long time.

One solution to avoid this problems is “memorization”. The memorization caches the intermediate calculation result and significantly reduce the ammount of computation. The computation cost is $O\bigl(N\bigr)$ when using memorization(Otsuki, AKiba(2020)). Here is the implementation of Fibonacci number calculation by recursion with memorization.

fun main(args: Array<String>) {
  val memo: MutableMap<Long, Long> = mutableMapOf(0L to 0L, 1L to 1L)

  fun fib(n: Long): Long =
    if (memo.contains(n)) {
      requireNotNull(memo[n])
    } else {
      memo[n] = fib(n - 1L) + fib(n - 2L)
      requireNotNull(memo[n])
    }

  check(fib(0L) == 0L)
  check(fib(1L) == 1L)
  check(fib(2L) == 1L)
  check(fib(50L) == 12586269025L)
}

By using memorization, I could calculate fast if the case of $ N = 50 $.

References

  1. Fibonacci number - Wikipedia
  2. Otsuki, Akiba, 問題解決力を鍛える!アルゴリズムとデータ構造, 2020, Kodansha, Inc.
  3. 100番目までのフィボナッチ数列 - すぐる学習会 -

About me

Experienced software developer. Technical lead at Fuller, Inc. My speciality is developing Android native app. I'm living in Tsukuba Japan, with my family, dogs, and cats :)

Here is more detailed profile.