The Python library includes a memoization decorator in the functools module. We can use this module instead of creating our own callable object.

We can use this as follows:

from functools import lru_cache

@lru_cache()
def pow6(x: int, n: int) -> int:
    if n == 0:
        return 1
    elif n % 2 == 1:
        return pow6(x, n-1) * x
    else:  # n % 2 == 0:
        t = pow6(x, n // 2)
        return t * t

This code defines a function, pow6(), which is decorated with a Least Recently Used (LRU) cache. Previous requests are stored in a memoization cache. The idea behind an LRU cache is that the most recently made requests are kept and the oldest requests are quietly purged. We can use @lru_cache(256), for example, to limit the cache to 256 entries, thereby optimizing memory use.

Using timeit, we can see that 10,000 iterations of pow5() run in about 1 second, while the iterations for pow6() run in about 8 seconds.

What this also shows is that a trivial use of timeit can misstate the performance of the memoization algorithms. If each request is recomputing a previously cached answer, only the first iteration – with an empty cache – performs the computation.