from matplotlib import pyplot
from time import time

oplossingen = {0:1, 1:1, 2:2}

def trappen(n):
    # basisgeval: als het al berekent is, geef de oplossing terug
    if n in oplossingen:
        return oplossingen[n]
        
    # functie roept zichzelf terug op met kleinere prameters en slaat het resultaat op
    else:
        aantal_stappen = trappen(n - 1) + trappen(n - 2)
        oplossingen[n] = aantal_stappen
        return aantal_stappen


# testprogramma
treden = [0, 1, 2, 3, 4, 5, 10, 27]

for n in treden:
    print(f"Een trap met {n} treden kun je op {trappen(n)} manieren beklimmen.")

#------------------------------------
# tijdsmeting
#------------------------------------
# from matplotlib import pyplot
# from time import time
# treden = list(range(700))
# tijden = []
# for n in treden:
#    oplossingen = {0:1, 1:1, 2:2}
#    tijd_begin = time()
#    trappen(n)
#    duur = time() - tijd_begin
#    tijden.append(duur)
#    
# pyplot.plot(treden, tijden)
# pyplot.show()
#------------------------------------