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: