Programmierung - Was macht die Funktion?
def funktion(zahl):
if zahl < 2:
return zahl
else:
return funktion(zahl -1) + funktion(zahl - 2)
ergebnis = funktion(10)
print(ergebnis)
Kann mir jemand erklären, was hier passiert? Warum ist das Ergebnis 55?
4 Antworten
Die Funktion „funktion“ ist im Grunde eine rekursive Implementation der Fibonnacci-Folge...
https://de.wikipedia.org/wiki/Fibonacci-Folge
[...zumindest, wenn man natürliche Zahlen als Argument einsetzt.]
Wenn man „funktion(n)“ kurz als...
... schreibt, so erhält man...
Im konkreten Beispiel mit n = 10... Da 10 ≥ 2 ist, erhält man...
Nun muss als nächstes herausgefunden werden, was f₉ bzw. f₈ ist. Für f₉ muss herausgefunden werden, was f₈ und f₇ ist... Und so weiter.
[...]
Das Programm muss immer tiefer gehen, da es ja immer weiter Funktionswerte braucht, die noch nicht bekannt sind... Bis das Programm auf f₁ = 1 und f₀ = 0 trifft, die direkt festgelegt sind, ohne sich auf andere Funktionswerte zu beziehen. Da das Programm nun die Werte für f₁ und f₀ kennt, kann es diese für die Berechnung von f₂ verwenden...
Und nun geht es umgekehrt wieder nach oben, bis das Programm die Werte f₉ = 34 und f₈ = 21 gefunden hat, und dann schließlich...
... berechnen kann. [Die Zahl 55 wird dann der Variable „ergebnis“ zugewiesen, und dann dieser gespeicherte Wert mit der „print“-Funktion ausgegeben.]
Sie berechnet rekursiv die sogenannte Fibonacci-Folge.
funktion(0) = 0
funktion(1) = 1
funktion(2) = funktion(1)+funktion(0) = 1 + 0 = 1
funktion(3) = funktion(2)+funktion(1) = 1 + 1 = 2
funktion(4) = funktion(3)+funktion(2) = 2 + 1 = 3
funktion(5) = funktion(4)+funktion(3) = 3 + 2 = 5
funktion(6) = funktion(5)+funktion(4) = 5 + 3 = 8
funktion(7) = funktion(6)+funktion(5) = 8 + 5 = 13
funktion(8) = funktion(7)+funktion(6) = 13 + 8 = 21
funktion(9) = funktion(8)+funktion(7) = 21 + 13 = 34
funktion(10) = funktion(9)+funktion(8) = 34 + 21 = 55
Halli hallo,
das ist ein Algorithmus, um die Fibonacci-Zahl mit dem index des übergebenen Parameters.
Grüße && schönes WE