def memoize(f):
    #we use a DICTIONARY to store lookup values
    memo = {}
    def helper(x):
        if x not in memo:
            #add a new entry to the dictionary:
            print("calling function, x = ",x)
            memo[x] = f(x)
        else:
            print("calling memo, x = ",x)
        return memo[x]
    return helper

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

def fiba(n):
    global rCount 
    rCount = rCount+1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fiba(n-1) + fiba(n-2)

rCount=0
fib = memoize(fib)
#experiment with different inputs (below we
#try 36) to see that fiba is much slower than
#the memoized function fib
print(fiba(36))
print(fib(36))
print(' Function fiba called ', rCount, ' times.')