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
@lru_cache(maxsize=None)
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.