An Introduction to Python memorisation using functools

December 29, 2019

In Python you can trade time-complexity for an increase in the memory usage of a Python script. For example, the factorial function is defined recursively f(5) = 5! = 5 * 4 * 3 * 2 * 1, where 1 is the base-case. But, what happens if we remember what 4! is equal to, by definition 5! is simply 5 * memo{4}

You could just use a Python dictionary like so:

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