# Memoization For Beginners

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:

 ``````1 2 3 4 5 6 7 8 `````` ``````# 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.

 ``````1 2 3 `````` ``````>>> 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````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()`.

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` `````` \$ 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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` ``````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:

 ``````1 2 3 4 5 6 `````` `````` \$ 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!