##Fibonacci served 7 ways
##A collection of functions for calculating Fibonacci numbers

##1  Recursion method on two lines
def fib_rec1(n):
    if n < 2: return n  
    return fib_rec1(n - 1) + fib_rec1(n - 2)

##2  Recursion method on one line
def fib_rec2( n ):
    return n if n < 2 else fib_rec2( n - 1 ) + fib_rec2( n - 2 )

##3  Using the Binet formula
##However values become non integral due to approximate square root
##calculations and must be rounded
def fib_Binet(n):
    fi = (1 + math.sqrt(5))/2
    return int((fi**n - (-fi)**-n)/math.sqrt(5))

##4  First iterative method
def fib_iterative1(n):
    i=0
    j=1
    if n==0:
        return n
    else:
        for m in range(1,n):
            k=i+j
            i=j
            j=k
        return j

##5  Second iterative method
def fib_iterative2(n):
    i,j = 1,0
    for k in range(1,n + 1):
        i,j = j, i + j
    return j

##6  Creating a Python list
def fib_list(n):
   fibValues = [0,1]
   for i in range(2,n+1):
      fibValues.append(fibValues[i-1] + fibValues[i-2])
   return fibValues[n]


##7  Using a Python dictionary.
##We can use a dictionary to save previous computations in a function call,
##replacing all the repeated recursion computations by fast dictionary look-ups.
##We check to see if the key has already been computed,
##and if it has, we look it up.
##This is much faster than any recursion method
##which forgets each value immediately after using it.
fibTable = {0:0, 1:1}
def fib_dict(n):
  
   if n in fibTable:
      return fibTable[n]
   else:
      fibTable[n] = fib_dict(n-1) + fib_dict(n-2)
      return fibTable[n]

#main program    
import time
import math

print("***Time comparisons of various algorithms for calculating Fibonacci numbers***")
print()
choice="y"
while choice=="y":
    select=1
    n=int(input("""
We label \"0\" as the first with position 0.
Note that the recursion algorithms may take excessive times for terms > 35
We will time 7 different algorithms!
Which Fibonacci term do you wish to calculate? """) )
    print()
    while select<8:
        start_time = time.clock()
        
        if select==1:
            print(select,"Recursion algorithm One")
            print("Fibonacci number",n,"is",fib_rec1(n))
        elif select==2:
            print(select,"Recursion algorithm Two")
            print("Fibonacci number",n,"is",fib_rec2(n))
        elif select==3:
            print(select,"Binet formula algorithm")
            print("Fibonacci number",n,"is",fib_Binet(n))
        elif select==4:
            print(select,"First iteration algorithm")
            print("Fibonacci number",n,"is",fib_iterative1(n))
        elif select==5:
            print(select,"Second iteration algorithm")
            print("Fibonacci number",n,"is",fib_iterative2(n))
        elif select==6:        
             print(select,"List based algorithm")
             print("Fibonacci number",n,"is",fib_list(n))
        elif select==7:
            print(select,"Dictionary based algorithm")
            print("Fibonacci number",n,"is",fib_dict(n))
  
        
        print (time.clock() - start_time, "seconds")
        print()
        select+=1
    choice=input("Do you wish to run this again? ")