Memoization

Applies to: general, python

Memoization caches a function's results so repeated calls with the same arguments are instant. It turns exponential recursive blowups (like naive Fibonacci) into linear time, the core idea behind dynamic programming.

from functools import lru_cache
@lru_cache
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

See also: recursion, hash-map, big-o