import timeit

n = 35

# naive recursive
def fib(n):
    if n <= 1: 
        f = n
    else: 
        f = fib(n-1) + fib(n-2)
    return f

print(f'naive recursive: {timeit.timeit(lambda: fib(n), number=1)}')

# memoized recursive (DP)
def fib(n):
    memo = {} # {1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34}
    
    def fib_(n):
        if n in memo:
            return memo[n]
        if n <= 1:
            f = n
        else: 
            f = fib_(n-1) + fib_(n-2)
        memo[n] = f
        return f
        
    return fib_(n)

print(f'memoized recursive: {timeit.timeit(lambda: fib(n), number=1)}')

# bottom-up iterative using dict memo (DP)
def fib(n):
    memo = {} # {1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34}

    for k in range(n+1):
        if k <= 1:
            f = k
        else:
            f = memo[k-2] + memo[k-1]
        memo[k] = f
        
    return memo[n]
            
print(f'iterative, dict: {timeit.timeit(lambda: fib(n), number=1)}')

# bottom-up iterative using list memo (DP)
def fib(n):
    memo = [None] * (n+1)

    for k in range(n+1):
        if k <= 1:
            f = k 
        else: 
            f = memo[k-2] + memo[k-1]
        memo[k] = f
        
    return memo[n]

print(f'iterative, fixed n list: {timeit.timeit(lambda: fib(n), number=1)}')

# bottom-up iterative using list memo, v2 (DP)
def fib(n):
    memo = []

    for k in range(n+1):
        if k <= 1:
            f = k 
        else: 
            f = memo[k-2] + memo[k-1]
        memo.append(f)
        
    return memo[n]

print(f'iterative, []: {timeit.timeit(lambda: fib(n), number=1)}')

# infinite generator
def fib():
    a, b = 0, 1
    while True:
        yield a 
        a, b = b, a + b 

# find the nth fib number, v1
nth_fib = fib()
def gen_fib(): 
    for i in range(n):
        f = next(nth_fib)
    return f

print(f'generator: {timeit.timeit(gen_fib, number=1)}')