# File timer.py
# Time the iterative and recursive versions of computing a Fibonacci number
#
# Matt Bishop, ECS 10, Spring 2014
#
import timeit

#
# recursively compute the nth Fibonacci number
#
def rfib(n):
    # base cases: f0 = 0, f1 = 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # recursion: fn = fn-1 + fn-2
    return rfib(n-1) + rfib(n-2)

#
# Iteratively compute the nth Fibonacci number
#
def fib(n):
    # if f0 or f1, no iteration needed
    if n == 0:
    	return 0
    elif n == 1:
    	return 1
    # okay, we need to iterate; initialize the sequence
    fnm2 = 0
    fnm1 = 1
    for i in range(n-2):
    	# get next Fibonacci number
       	fn = fnm1 + fnm2
       	# advance in sequence
       	fnm2 = fnm1
       	fnm1 = fn
    # return the nth number
    return fn

# here's the dictionary -- empty initially
fibdict = {}

# compute the nth Fibonacci number
# and store it in the dictionary
def rfibmemo(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] = rfibmemo(n-1) + rfibmemo(n-2)
    return fibdict[n]

#
# now time them
#
def main():
    # input number
    try:
        n = int(input("Fibonacci sequence from f0 to f(enter number): "))
    except:
        print("Need an integer")
        return

    # it better be non-negative!
    if n < 0:
        print("Need a non-negative integer")
        return
    # run each and print the time
    print("Iterative: %e" % timeit.timeit('fib(' + str(n) +')', setup="from __main__ import fib", number=1))
    print("Recursive: %e" % timeit.timeit('rfib(' + str(n) +')', setup="from __main__ import rfib", number=1))
    print("Memoed: %e" % timeit.timeit('rfibmemo(' + str(n) +')', setup="from __main__ import rfibmemo", number=1))

#
# and they're off!
#
main()