# fibonacci
#    fib(n) = fib(n-1) + fib(n-2)

count = 0

def fib(n):
    global count
    if( n == 0 ): return 0
    if( n == 1 ): return 1
    count += 1
    return fib(n-1) + fib(n-2)   #  recursive call

print(fib(10),count)

# memoize fib  with n < 20

memo = [0] * 20   # create array size 20, all zero
count2 = 0

def fibm(n):
    global count2
    if( n == 0 ):
        memo[0] = 0
        return 0
    if( n == 1 ):
        memo[1] = 1
        return 1
    if( memo[n] != 0 ):
        return memo[n]
    count2 += 1
    memo[n] = fibm(n-1) + fibm(n-2)   # recursive call
    return memo[n]

print(fibm(10),count2)
print(memo)

# 55 88
# 55 9
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# >>>