import time
from matplotlib.pylab import *

def fib1(n):
    if n <= 1: return n
    return fib1(n-1)+fib1(n-2)

def fib2(n, a=0, b=1):
    if n == 0: return a
    elif n == 1: return b
    else: return fib2(n-1, b, a+b)

t1 = []
for i in range(1,18):
    before = time.clock()
    for r in range(10000): fib1(i)
    after = time.clock()
    t1.append((after-before)/10000)
    print "n=%d t1=%e" % (i, t1[-1])

t2 = []
for i in range(1,40):
    before = time.clock()
    for r in range(100000): fib2(i)
    after = time.clock()
    t2.append((after-before)/100000)
    print "n=%d t2=%e" % (i, t2[-1])

subplot(2,2,1)
plot(t1, 'o-', t2, 'x-')

subplot(2,2,2)
semilogx(t1, 'o-', t2, 'x-')

subplot(2,2,3)
semilogy(t1, 'o-', t2, 'x-')

subplot(2,2,4)
loglog(t1, 'o-', t2, 'x-')
show()
