# 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

#
# now time them
#
def main():
    # input number
    try:
        n = int(input("Fibonacci sequence from f0 to f: "))
    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))

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