okuzawatsの日記

Android / Kotlin Enthusiast 🤖

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:

#Python

About me 😎

profile

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

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

👉 もっと詳しく

Writing 📝

Android MVVMアーキテクチャ入門

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

👉 もっと詳しく

See Also 👀