Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
public static long fibo(long n) {
if (n <= 2) {
return 1;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}
Der else-Teil besagt ja im Prinzip, dass wenn man z.B. die 7. Stelle der Fiboreihe herausfinden möchte, dass in dem Fall die 6. Stelle + die 5. Stelle gleich der 7. Stelle sind. Wenn ich n jetzt 7 zuweise, wird (7-1) = 6 + (7-2) = 5 = 11 berechnet. Oder wird n direkt auch für (n-2) geändert sobald 7-1 gerechnet worden ist? Also ich habe das rekursive Prinzip hier nicht ganz durchschaut...
Es wird das Ergebnis der Fibonacci Rechnung für 7-1 mit dem Ergebnis der Fibonacci Rechnung für 7-2 berechnet.
Stellen ist auch der komplett falsche Begriff.
Wenn du den Wert für fibo(7) berechnen willst, dann sagt die Methode:
- Berechne mir den Wert von fibo(6) und fibo(5) und addiere die Ergebnisse
Wenn du den Wert für fibo(6) berechnen willst, dann sagt die Methode:
- Berechne mir den Wert von fibo(5) und fibo(4) und addiere die Ergebnisse
usw.
Erst, wenn du den Wert für einen Wert kleiner gleich 2 berechen willst, passiert was anderes
Wenn du den Wert für fibo(2) berechnen willst, dann sagt die Methode: Der Wert ist 1
Wenn du den Wert für fibo(1) berechnen willst, dann sagt die Methode: Der Wert ist 1
Am einfachsten ist es, wenn du dir einen Binärbaum dazu vorstellst, um es zu visualisieren. Jeder einzelne fib()-Aufruf spannt einen eigenen Teilbaum auf...
Schreib es Dir doch erst einmal als Reihe auf. Das ist ja nichts anderes als eine Reihe, die mit 1, 1 anfängt und dann ist jedes Element, das folgt, die Summe der Vorgänger:
1, 1, 2, 3, 5, 8, 13, 21, ....
Und dieses Vorgehen wird dann nur entsprechend abgebildet:
ist n <= 2 dann ist es 1.
Ansonsten die Summe der zwei Vorgänger.
Das habe ich auch gemacht. Wenn jetzt n = 5, dann ist der Rückgabewert in dem Fall ja auch 5. Ich verstehe nur nicht wie genau der Code dabei vorgeht...
Was n angeht und das Ergebnis, das bei jeweiligem n herauskommt habe ich verstanden.
fibo(n-1) + fibo(n-2)
Bsp.: fibo(5-1) + fibo(5-2)..., aber so geht es ja nicht...
Jetzt habe ich mich angemeldet per Handy und jetzt habe ich einen neuen Acc erstellt ohne es zu wollen, habe auf anmelden geklickt und hatte nur ne falsche mail eingegeben und jetzt das 😀D Weiß jemand wie ich den löschen kann?
Somit wird jetzt fibo(5-1) aufgerufen:
2. fibo(n = 4):
- n <= 2 ? Nein
- Ergebnis: fibo(4-1) + fibo(4-2)
Somit wird jetzt fibo(4-1) aufgerufen:
3. fibo(n = 3):
- n <= 2 ? Nein
- Ergebnis: fibo(3-1) + fibo(3-2)
Somit wird jetzt fibo(3-1) aufgerufen:
4. fibo(n = 2):
- n <= 2 ? Ja: Ergebnis = 1.
Somit haben wir jetzt bei dem Ablauf bei 3. als Teil-Ergebnis:
3. fibo(n = 3):
- n <= 2 ? Nein
- Ergebnis: fibo(3-1) 1 + fibo(3-2)
5. fibo(n = 3-2 = 1)
- n <= 2 ? Ja: Ergebnis: 1
Somit kommt das Ergebnis jetzt bei 3. rein:
3. fibo(n = 3):
- n <= 2 ? Nein
- Ergebnis: fibo(3-1) 1 + fibo(3-2) 1 = 2
Das Ergebnis aus 3. kommt nun bei 2. rein:
2. fibo(n = 4):
- n <= 2 ? Nein
- Ergebnis: fibo(4-1) 2 + fibo(4-2)
Da geht es jetzt so weiter - es wird halt jetzt fibo(4-2) berechnet.
und so weiter und so weiter ... Bis dann bei der Berechnung in 1. beide Ergebnisse zurück sind und die Summe als Ergebnis berechnet werden kann.
Jetzt habe ich mich angemeldet per Handy und jetzt habe ich einen neuen Acc erstellt ohne es zu wollen, habe auf anmelden geklickt und hatte nur ne falsche mail eingegeben und jetzt das 😀D Weiß jemand wie ich den löschen kann?
Wie würde man denn hier weiter vorgehen? 4-2 würde ja wieder zu dem Ergebnis von 1 führen. Sprich 2 + 1. Nun muss ich jetzt wohin springen? Finde das gar nicht so leicht. Bis zum Ende habe ich alles verstanden. Jetzt geht es ja so weiter. Nur dieses hin-und her switchen verwirrt mich jetzt etwas. Und wieso kommt das Ergebnis aus 3. jetzt überhaupt in 2. rein?
Das Ergebnis aus 3. kommt nun bei 2. rein:
2. fibo(n = 4):
- n <= 2 ? Nein
- Ergebnis: fibo(4-1) 2 + fibo(4-2)
Da geht es jetzt so weiter - es wird halt jetzt fibo(4-2) berechnet.
und so weiter und so weiter ... Bis dann bei der Berechnung in 1. beide Ergebnisse zurück sind und die Summe als Ergebnis berechnet werden kann.
Nun merkst Du: Du musst fibo(4) berechnen. Daher: Unterstreiche das fibo(4) (Das ist dann sozusagen sowas wie die Rücksprungadresse.
Dann: Neues Papier!
fibo(4)
========
4 <=2 nein
....
Dann kommt fibo(3) wieder ein neues Papier:
fibo(3)
=======
3 <= 2? Nein
Ergebnis: fibo(2) + fibo(1)
Du unterstreicht fibo (2) und neues Papier:
fibo(2)
=====
2 <= 2: Ja ==> 1
Nun hast Du ein Ergebnis, d.h. dieses Papier geht vom Stapel und das, was unterstrichen war, wird nun durchgestrichen und die 1 kommt dahin:
Und nun wird fibo(1) unterstrichen, neues Papier: fibo(1) schreiben und so verfahren ...
Damit hast Du 1;1 durchgespielt, was auch der Compiler macht. Der Compiler hat auch einen Stack und legt die Variablen und so immer wieder auf den Stack bei den Aufrufen. Und am Ende hast Du mehrfach fibo(1)m fibo(2) u.s.w. berechnet. Das ist aber egal. Das macht der Rechner mehrfach!
Um das zu verdeutlichen: Bau Ausgaben ein! Du kannst das ja etwas aufteilen:
Java:
public static long fibo(long n) {
if (n <= 2) {
System.out.println("fibo(" + n + ") = 1");
return 1;
} else {
long n1 = fibo(n-1);
long n2 = fibo(n-2);
System.out.println("fibo(" + n + ") = " + n1 + " + " + n2 + " = " + (n1+n2));
return n1 + n2;
}
}
Dann siehst Du, was alles berechnet wird und wie oft...
