from time import time

oplossingen = [0, 1, 2]

def trappen(n):
     # basisgeval: als het al berekent is, geef de oplossing terug
    if n < len(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.append(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, 2]
#    tijd_begin = time()
#    trappen(n)
#    duur = time() - tijd_begin
#    tijden.append(duur)
#    
# pyplot.plot(treden, tijden)
# pyplot.show()
#------------------------------------