# Program to compute the first 100 numbers of the Fibonacci series
# Matt Bishop, ECS 10, Spring 2014

# idea: every time we compute a Fibonacci number fn, we store n and fn
# in a dictionary; n is the key, fn the value
# then, rather than recompute it, we look it up and if not there, compute
# it and put it in the dictionary
#
# here's the dictionary -- empty initially
fibdict = {}

# compute the nth Fibonacci number
# and store it in the dictionary
def fib(n):
    global fibdict
    #
    # look it up first; if already computed, return it
    #
    if n in fibdict:
        return fibdict[n]
    #
    # nope -- so recompute it
    #
    # base case: f0 = 0, f1 = 1
    if n == 0:
        fibdict[0] = 0
        return 0
    elif n == 1:
        fibdict[1] = 1
        return 1
    # recursive case: fn+2 = fn+1 + fn
    # as we computed it, we also store it
    fibdict[n] = fib(n-1) + fib(n-2)
    return fibdict[n]

#
# the heart of the program
#
def main():
	# say how many numbers are to be printed
	count = 100

	# compute the sequence and print the terms
	for i in range(count-2):
                # get next Fibonacci number and
		# announce it
		print("Fibonacci number", i+1, "is", fib(i))
		
main()