import time

def f(n):
	if n < 0:
		return "n cannot be less than 0"
	elif n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return f(n - 1) + f(n - 2)

def f2(n, memo={}):
    if n < 0:
        return "n cannot be less than to 0"
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = f2(n-1) + f2(n-2)
        return memo[n]

def f3(n):
    a = 0
    b = 1
    i =0
    while i < n:
        a, b = b, a + b
        i += 1
    return a

t = time.time()
print(f3(500))
t2 = time.time()
print(t2 - t, "s")
t = time.time()
print(f2(500))
t2 = time.time()
print(t2 - t, "s")