Memos: Example with Fibonacci Number
When solving a recurrence problem, the call stack quickly gets deeper. Even a simple calculation of Fibonacci numbers, the amount of computation soon increases quickly. With this simple implementation of fibonacci
, even fibonacci(100)
takes so long time to calculate. This is because fibonacci(n)
for same n
is called repeatedly. This implementation is not efficient.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
In this situation, “memos” would make the calculation much more efficient. With Python, storing the value already computed to a dictionary will enable the result to be reused. Once computed and stored in the dictionary (“memos”), the value for n
is calculated with O(1)
.
fibonacci_memos = {0: 0, 1: 1}
def fibonacci(n):
if n in fibonacci_memos:
return fibonacci_memos[n]
fibonacci_n = fibonacci(n - 1) + fibonacci(n - 2)
fibonacci_memos[n] = fibonacci_n
return fibonacci_n
References:
About me 😎

茨城県つくば市在住のソフトウェアエンジニアです。専門領域はAndroidアプリ開発で、特にアーキテクチャに興味があります。某社でAndroidアプリ開発のテックリードをしています。
Jetpack ComposeによるAndroid MVVMアーキテクチャ入門の著者です。
👉 もっと詳しく
Writing 📝
Android MVVMアーキテクチャ入門
Androidアプリ開発の初学者に向けた、MVVM(Model-View-ViewModel)アーキテクチャの入門書を書きました。初学者の方を確実にネクストレベルに引き上げる技術書です。
👉 もっと詳しく