memoization

what is it?

memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again

caching fibonacci numbers

the following function returns the numth fibonacci number

def fibonacci(num):
    if num < 2:
        return num
    return fibonacci(num - 1) + fibonacci(num - 2)

it’s very expensive, because the code is recursive and keeps recalculating fibonacci numbers previously calculated

one solution is to use a cache decorator

import functools
 
def cache(func):
    """Keep a cache of previous function calls"""
    @functools.wraps(func)
    def wrapper_cache(*args, **kwargs):
        cache_key = args + tuple(kwargs.items())
        if cache_key not in wrapper_cache.cache:
            wrapper_cache.cache[cache_key] = func(*args, **kwargs)
        return wrapper_cache.cache[cache_key]
    wrapper_cache.cache = {}
    return wrapper_cache
 
@cache
def fibonacci(num):
    if num < 2:
        return num
    return fibonacci(num - 1) + fibonacci(num - 2)

NB rather use @functools.lru_cache or @functools.cache instead of writing your own cache decorator

import functools
 
@functools.lru_cache(maxsize=4)
def fibonacci(num):
    if num < 2:
        value = num
    else:
        value = fibonacci(num - 1) + fibonacci(num - 2)
    print(f"Calculated fibonacci({num}) = {value}")
    return value

maxsize parameter specifies how many recent calls are cached. the default value is 128, but you can specify maxsize=None to cache all function calls