# File timer.py
# Time the iterative and recursive versions of computing a Fibonacci number
#
# Matt Bishop, ECS 10, Fall 2012
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
#
print("Iterative: %e" % timeit.timeit('fib(40)', setup="from __main__ import fib", number=1))
print("Recursive: %e" % timeit.timeit('rfib(40)', setup="from __main__ import rfib", number=1))