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

print([fib(n) for n in range(10)])

# 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([fib(n) for n in range(10)])

# 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([fib(n) for n in range(10)])

# 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([fib(n) for n in range(10)])

# 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([fib(n) for n in range(10)])


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

fibs = fib()
# generate first 5 fib numbers
print([next(fibs) for _ in range(5)], end=' ') 
# generate next 5 fib numbers
print([next(fibs) for _ in range(5)])

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

# find the nth fib number, v2
nth_fib = fib()
n = 10
print([next(nth_fib) for _ in range(n)][-1])