"""
 fib - 2nd version
"""
steps = 0

cache = {}

def fib(n):
    # MEMOIZED !
    if not n in cache:
        cache[n] = _fib(n)
    return cache[n]

def _fib(n):
    """ Return the n'th fibonnaci number """
    
    global steps
    steps = steps + 1
    
    if n < 2:
        steps = steps + 1
        return 1
    else:
        steps = steps + 1
        return fib(n-1) + fib(n-2)

f = fib(40)
print("fib(20) is ", f)
print("number of steps is ", steps)