Fibonacci Code verstehen

[ShivaWookie]

Hallo,

ich habe diesen Code zur Berechnung von Fibonacci Zahlen gefunden und möchte ihn auch verstehen. Mir ist irgendwie nicht ganz klar, wie der Code funktioniert bzw. wie er zusammenrechnet, wie er auf die Zahlen kommt und was bei jedem Schritt in fib(n-1) + fib(n-2) gespeichert wird. Ich stehe bestimmt auf dem Schlauch und die Antwort ist ganz einfach und logisch aber ich komm einfach nicht drauf.

def fib(n):
.....if n == 1 or n == 2:
.........return n-1
.....return fib(n -1) + fib(n-2)

.....for i in range(1,10):
............print(fib(i))

Danke schonmal

[snafu]

Lass doch erstmal das range() weg und rufe die Funktion mit ein paar kleinen Werten auf, z.B. fib(3).

Wenn es dir dann gedanklich noch nicht klargeworden ist, dann füge ein print(n) als erste Zeile in die Funktion ein, um bei jedem Rekursionsschritt den jeweiligen Wert von n zu sehen.

Vom Prinzip her geht der Programmfluss die Reihe halt von hinten nach vorne durch, wenn man so will, da er mit den größten Werten beginnt.

[ThomasL]

Ich gehe davon aus, die Folge selber ist dir bekannt. https://de.wikipedia.org/wiki/Fibonacci-Folge
und zu Rekursion steht hier etwas https://de.wikipedia.org/wiki/Rekursion

[ShivaWookie]

@ snafu das habe ich auch schon gemacht. Geholfen hat es leider nicht wirklich...
ich habe jetzt selber einen Code programmiert:
y = 1
print(y)
fib1 = 0
fib2 = 1
x = 0
result = 0

while x < 10:
.....x = x + 1
.....result = fib1 + fib2
.....fib1 = fib2
.....fib2 = result

Dort sehe ich genau was passiert und wie die Variablen fib1 und fib2 einen neuen Wert zugewiesen bekommen.
Bei dem anderen wird das, finde ich, nicht ganz so ersichtlich....vielleicht weil sie rekursiv ist

@ThomasL die Folge ist mir bekannt ja und natürlich gibt es andere Wege die Reihe zu programmieren s.o.
Ich wollte nur den Code richtig verstehen.

Ich bin noch Anfängerin und möchte so viel wie möglich mitnehmen.

Ich danke euch beiden sehr für die Hilfe!

[__blackjack__]

@ShivaWookie: Benutze bitte die Code-Tags ([ code ] ohne die Leerzeichen, kann man auch über die Schaltfläche mit der Beschriftung </> einfügen), damit die Einrückung erhalten bleibt. Das ist einfacher zu lesen und für Dich auch einfacher zu schreiben im Vergleich zu den Punkten an den Zeilenanfängen.

Die ersten beiden Zeilen mit `y` machen keinen Sinn weil die mit dem Rest des Codes nichts zu tun haben.

Innerhalb der Schleife würde eine Ausgabe Sinn machen, damit man auch wirklich etwas sieht.

`result` muss vor der Schleife nichts zugewiesen werden. Man kann das in Python auch etwas kompakter, ohne eine Zwischenvariable schreiben:

Code: Alles auswählen

        fib1, fib2 = fib2, fib1 + fib2

Bei Schleifen wo man vorher schon weiss wie oft sie durchlaufen werden sollen, verwendet man nicht ``while`` sondern ``for``.

Als Programm dann:

Code: Alles auswählen

#!/usr/bin/env python3


def main():
    fib1, fib2 = 0, 1
    for _ in range(10):
        print(fib1)
        fib1, fib2 = fib2, fib1 + fib2


if __name__ == '__main__':
    main()

[ThomasL]

@ThomasL die Folge ist mir bekannt ja und natürlich gibt es andere Wege die Reihe zu programmieren s.o.
Ich wollte nur den Code richtig verstehen.

Du hast ein Problem den rekursiven Code/ die Methode zu verstehen und ersetzt ihn deshalb durch die iterative Methode?

Ich persönlich finde die rekursive Methode einfacher zu verstehen als jede iterative,
da sie genau die Definition und das rekursive Bildungsgesetz umsetzt/abbildet.

Ungeachtet dessen kannst du die Folge folgenderweise trivial anschaulich aufbauen:

fib(n) = fib(n-1) + fib(n-2) mit f(1) = 1 und f(2) = 1

fib(3) = fib(2)+fib(1) = 1+1 = 2
fib(4) = fib(3)+fib(2) = fib(2)+fib(1)+1 = 1+1+1 = 3
fib(5) = fib(4)+fib(3) = fib(3)+fib(2)+fib(2)+fib(1) = fib(2)+fib(1)+1+1+1 = 1+1+1+1+1 = 5
fib(6) = fib(5)+fib(4) = fib(4)+fib(3)+fib(3)+fib(2) = fib(3)+fib(2)+fib(2)+fib(1)+fib(2)+fib(1)+1 = fib(2)+fib(1)+1+1+1+1+1+1 = 1+1+1+1+1+1+1+1 = 8
usw
usw

Eine durchaus nett gemachtes Erklärvideo dazu findest du hier:
https://www.youtube.com/watch?v=Qk0zUZW-U_M