In [ ]:

    

def fib(n):
    global numCalls
    numCalls += 1
    print ('fib called with', n)
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)
numCalls = 0
fib(5)


    

In [ ]:

    

def fib(n):
    memo = { 0:0, 1:1}
    return fastFib(n, memo)
    
def fastFib(n, memo):
    global numCalls
    numCalls +=1
    #print ('fastFib call with', n)
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    return memo[n]

numCalls = 0
fib(1000)


    

In [ ]:

    

def fibHeavy(n):
    memo = [0, 1]
    for i in range(2, n + 1):
        memo.append(memo[i-1] + memo[i-2])
    print(len(memo))
    return memo[n]

#fibHeavy(1000000)


    

In [ ]:

    

def fibLite(n):
    if n < 2:
        return n
    memo = { 0:0, 1:1, 'tmp':0 }
    for i in range(2, n + 1):
        memo['tmp'] = memo[1]
        memo[1] = memo[0] + memo[1]
        memo[0] = memo['tmp']
    print(len(memo))
    return memo[1]


    

In [ ]:

    

n = 10000000


    

In [ ]:

    

print(fibLite(n))


    

In [ ]:

    

print("fibHeavy",fibHeavy(n))


    

In [ ]: