memoization in fib examples

memoization.py

# visualize the function runtime
# using https://pythontutor.com/composingprograms.html#mode=edit

def fib0(n):
    if n < 2: return n
    return fib0(n - 1) + fib0(n - 2)

fib0(3)

def fib1(n, m={}):
    if n < 2: return n
    if n not in m:
        m[n] = fib1(n - 1) + fib1(n - 2)
    return m[n]

fib1(3)

def memoization(func):
    m = {}
    def wrapper(n):
        if n not in m:
            m[n] = func(n)
        return m[n]
    return wrapper

@memoization
def fib2(n):
    if n < 2: return n
    return fib2(n - 1) + fib2(n - 2)

fib2(3)