An Introduction to Python Memorisation

December 29, 2019

As we all know recursion and looping can be used interchangeably but one type of problem may lead one to be used. Mathematical formulae are often defined recursively so it is easier to simply ‘copy’ the formulae into code. A common example is the factorial function, like 5! = 120, and this is defined mathematically like: n! = n * (n - 1) * (n - 2) * .. * 1

But this brings about a problem? Can you see it? If you were to do this for a large number you would be computing the same value many times. Wouldn’t it better if you could ‘memorize’ a value?

You could just use a Python dictionary like:

memo = {0:1}
def factorial(n):
    if n < 2:
        return memo[0]
    if n not in memo:
        memo[n] = n * factorial(n-1)
    return memo[n]

Python already has this built-in by importing functools from the standard library. Here’s the Fibonacci algorithm using LRU cache:

from functools import lru_cache

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

This just goes to show it is still possible to write performant functions that are easier to understand than there iterative equivalent.

Back to top