def fib(n):
if n < 0:
return None
if n == 0:
return 0
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
memo = {}
def fib_memo(n):
result = None
if n in memo:
result = memo[n]
elif n == 0 or n == 1:
result = n
else:
result = fib_memo(n-1) + fib_memo(n-2)
memo[n] = result
return result
print(fib(9))
print(fib_memo(9))
print(fib(20))#6765
print(fib_memo(20))