okuzawatsの日記

Android / Kotlin Enthusiast 🤖

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番目までのフィボナッチ数列 - すぐる学習会 -

#Kotlin

About me 😎

profile

茨城県つくば市在住のソフトウェアエンジニアです。専門領域はAndroidアプリ開発で、特にアーキテクチャに興味があります。某社でAndroidアプリ開発のテックリードをしています。

Jetpack ComposeによるAndroid MVVMアーキテクチャ入門の著者です。

👉 もっと詳しく

Writing 📝

Android MVVMアーキテクチャ入門

Androidアプリ開発の初学者に向けた、MVVM(Model-View-ViewModel)アーキテクチャの入門書を書きました。初学者の方を確実にネクストレベルに引き上げる技術書です。

👉 もっと詳しく

See Also 👀