def fib(n):
    if n in [1, 2]: return 1
    return fib(n - 1) + fib(n - 2)

%%time

fib(30)

def memoize(f):
    cache = {}
    def newf(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return newf

@memoize
def fib(n):
    if n in [1, 2]: return 1
    return fib(n - 1) + fib(n - 2)

%%time

fib(30)