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...