# Memos: Example with Fibonacci Number okuzawats

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: