import time, math
from matplotlib.pylab import *

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

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

t1 = []
t2 = []
fib = []
for i in range(4,18):
    before = time.clock()
    for r in range(10000): fib1(i)
    after = time.clock()
    t1.append((after-before)/10000)

    before = time.clock()
    for r in range(100000): fib2(i)
    after = time.clock()
    t2.append((after-before)/100000)

    # Die folgenden Zeile sollte so veraendert werden, dass sie die 
    # Zeilen fuer die LaTeXtabelle erzeugt
    print "N=%d fib2(N)=%d time(fib1(N))=%.1f time(fib2(N))=%.1f" \
        % (i, fib2(i), t1[-1]*1000000, t2[-1]*1000000)

semilogy(t1, 'o-', t2, 'x-')
legend(('fib1', 'fib2'))
xlabel('N')
ylabel('Laufzeit')
show()