# Time: O(n)
# Space = O(1)
def fib_iterative(N):
    if N == 0:
        return 0
    first = 0
    second = 1

    for i in range(1,N):
        third = first + second
        first = second
        second = third
    
    return second
    
# Time: O(2^n)
# Space: O(1) + stack
def fib_recursive(N):
    if N == 1:
        return 1
    if N == 0:
        return 0
    return fib_recursive(N-2) + fib_recursive(N-1)



assert 1 == fib_recursive(1)
assert 1 == fib_iterative(1)

assert 0 == fib_recursive(0)
assert 0 == fib_iterative(0)

assert 55 == fib_recursive(10)
assert 55 == fib_iterative(10)

assert 6765 == fib_recursive(20)
assert 6765 == fib_iterative(20)

assert 610 == fib_recursive(15)
assert 610 == fib_iterative(15)