In this tutorial we are going to look at a concept in computer science called
`memoization`

. This is a really cool concept that allows us to optimize the
runtime performance of some of our recursive algorithms by effectively caching
the results of previous computations so that they don’t have to be continuously
re-computed.

# The Fibonacci Example

Calculating Fibonacci in a recursive manner is quite possibly the best example
I’ve come across when it comes to showing the power of `memoization`

.

Imagine we had a function that computed the fibonacci number `n`

like so:

```
# Basic fibonacci function
# 1 + 1 + 2 + 3 + 5 + 8 + 13
def fib(n):
if n <= 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
```

When we then tried to run our `fib(7)`

function it would then compute the
following answer.

```
>>> import fibonacci
>>> fibonacci.fib(7)
13
```

Now the runtime complexity of this relatively simple function above would be
`O(2^n)`

which is incredibly inefficient as we start to compute larger and
larger fibonacci numbers.

# The Memoization Optimization

Through the use of `memoization`

we could effectively store the results of
previous computations. In order to store our results we will use a `dict`

in
Python.

```
def fib_with_memo(n, memo):
if n <= 0:
return 0
if n == 1:
return 1
if n not in memo:
print("Memo Computed")
memo[n] = fib_with_memo(n-1, memo) + fib_with_memo(n-2, memo)
return memo[n]
memo = {}
print(fib_with_memo(9, memo))
print(memo)
```

When you run this you should get the following output. As you can see from the
number of times `Memo Computed`

is printed out, we have been able to effectively
optimize the number of times we have to recursively call `fib()`

.

```
$ python3.6 fibonacci.py
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
34
{2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34}
```

We have been able to modify our program and change is runtime performance from
`O(2^N)`

to `O(N)`

which is a huge saving.

# Entire Program

The entire Python file can be found below.

```
import time
def fib(n):
if n <= 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
def fib_with_memo(n, memo):
if n <= 0:
return 0
if n == 1:
return 1
if n not in memo:
memo[n] = fib_with_memo(n-1, memo) + fib_with_memo(n-2, memo)
return memo[n]
memo = {}
start_time = time.time()
print(fib(35))
end_time = time.time()
print("Total Time: {}".format(end_time - start_time))
start_time = time.time()
print(fib_with_memo(35, memo))
end_time = time.time()
print("Total Time: {}".format(end_time - start_time))
print(memo)
```

The outputs of this are:

```
$ python3.6 fibonacci.py
9227465
Total Time: 7.323758840560913
9227465
Total Time: 0.00010204315185546875
{2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025,26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040, 31: 1346269, 32: 2178309, 33: 3524578, 34: 5702887, 35: 9227465}
```

As you can see the `memoized`

version of the fibonacci function returns in a
fraction of the time.

# Conclusion

If you found this tutorial useful or need further explanation then please feel free to let me know in the comments section below!

## Comments Section