Memoization

Twice, adv. Once too often. - Ambrosse Bierce, The Devil's Dictionary

From Chapter 8 of Python Algorithms by Magnus Lie Hetland

Memoization implies caching the return values of a function, in particular, a recursive one. If a call is made more than once with the same arguments, the result is simply returned from the cache.

The memo function implemented above can be used as a wrapper when defining our recursive algorithms:

You should try calling fib(100) with and without memoization. Kirk out!