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:

• Think Python: How to Think Like a Computer Scientist
• The Fibonacci numbers