import time

def fibr(n):
    """ recursive fibonacci """
    if n == 0: return 0
    if n == 1: return 1
    
    return fibr(n-1) + fibr(n-2)

#print fibr(5)

def fib(n):
    """ iterative fibonacci """
    if n == 0: return 0
    if n == 1: return 1
    
    f1 = 1                  # previous fibonacci number 
    f2 = 0                  # second previous fibonacci number
    
    for i in range(2,n+1):
        f = f1 + f2         # i'th fib number is the sum of previous two
        f2 = f1             # assign the previous number to the 2nd previous
        f1 = f              # assign the current number to the previous fib num
    
    return f

print fib(7)
    
# the iterative fibonacci is much faster than the recursive version
# because the recursive version has to solve multiple copies of the same
# subproblem 
    
"""
t1 = time.time()
fib(30)
t2 = time.time()

print t2 - t1

t1 = time.time()
fibr(30)
t2 = time.time()

print t2 - t1
"""