Fibonacci-Reihe

jono

Top Contributor
Hallo :)
Java:
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...
 

LimDul

Top Contributor
Es wird nicht (7-1) + (7-2) gerechnet.

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
 

lara99

Mitglied
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...
 
K

kneitzel

Gast
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.
 

jono

Top Contributor
Schreib es Dir doch erst einmal als Reihe auf.
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...
 

jono

Top Contributor
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 :DD Weiß jemand wie ich den löschen kann?
 
K

kneitzel

Gast
Dann spiel es doch einmal durch. Du hast ja den Code. Du rufst also auf fibo(5):

1. fibo(n = 5):
- n <= 2 ? Nein
- Ergebnis: fibo(5-1) + fibo(5-2)

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.
 
K

kneitzel

Gast
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 :DD Weiß jemand wie ich den löschen kann?
Schreib einfach eine Nachricht an @tbone78 - der räumt dann für Dich auf. Da der Post doppelt ist, kann er die Posts ggf. mit löschen.
 

jono

Top Contributor
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.
 
K

kneitzel

Gast
Nein,Das ist eine Stack basierte Abarbeitung. Also nimm Dir einen Stapel Papier.Jede fibo(x) Berechnung ist auf einem neuen Blatt!

Erstes Blatt:
fibo(5)
=====
5 <=2 ? Nein
Ergebnis: fibo(4) + fibo(3)

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:

fibo(3)
=======
3 <= 2? Nein
Ergebnis: fibo(2) 1 + fibo(1)

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...
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Abwandlung der Fibonacci Folge Java Basics - Anfänger-Themen 3
T Fibonacci mit einer Hilfsmethode berechnen Java Basics - Anfänger-Themen 10
123456789sssssaaaa Which is the best way to Print Fibonacci Series in Java? Java Basics - Anfänger-Themen 3
jhCDtGVjcZGcfzug Fibonacci Zahlen rekursiv und iterativ Java Basics - Anfänger-Themen 21
G Fibonacci Zahlenreihe Fehler Java Basics - Anfänger-Themen 4
D Fibonacci overflow integer Java Basics - Anfänger-Themen 8
B Fibonacci Zahlen dynamische Programmierung Java Basics - Anfänger-Themen 7
N Dynamisches Programmieren/Fibonacci Java Basics - Anfänger-Themen 1
V Fibonacci Folge Java Basics - Anfänger-Themen 4
S Fibonacci Zahlen rekursiv Java Basics - Anfänger-Themen 1
A Fibonacci Zahlen Java Basics - Anfänger-Themen 1
M Methoden Fibonacci-Folge Java Basics - Anfänger-Themen 6
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
P Fibonacci -Verallgemeintert Java Basics - Anfänger-Themen 2
K Methoden Fibonacci in Array mit rekursiver Methoden Java Basics - Anfänger-Themen 19
M Fibonacci rekursiv mittels Cache Java Basics - Anfänger-Themen 17
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
K Fibonacci Zahlen Java Basics - Anfänger-Themen 3
B Fibonacci Zahlen rekursiv Array Java Basics - Anfänger-Themen 12
M Fibonacci-Folge mit while-Schleife Java Basics - Anfänger-Themen 4
P fibonacci - do while Statement Logik Fehler Java Basics - Anfänger-Themen 5
A Fibonacci-numbers Java Basics - Anfänger-Themen 9
K Rekursion Fibonacci Java Basics - Anfänger-Themen 3
J Fibonacci Zahlen berechnen Java Basics - Anfänger-Themen 3
Z Fibonacci rekursiv meine Erklärung stimmt so? Java Basics - Anfänger-Themen 2
Z Fibonacci Array Erklärung Java Basics - Anfänger-Themen 5
A Gerade Terme der Fibonacci-Folge aufsummieren Java Basics - Anfänger-Themen 12
M Fibonacci, Fakultaet, GGT Java Basics - Anfänger-Themen 9
C Fibonacci Zahlen Java Basics - Anfänger-Themen 7
J Ausgabe der fibonacci Zahlen Java Basics - Anfänger-Themen 4
S Fibonacci Folge Java Basics - Anfänger-Themen 34
D Fibonacci Java Basics - Anfänger-Themen 11
M Fibonacci-Linear und Rekursiv Java Basics - Anfänger-Themen 14
W Fibonacci Zahlenberechnung Java Basics - Anfänger-Themen 9
X Fibonacci mit durchschnittlicher Zeit Java Basics - Anfänger-Themen 5
I Fibonacci-Folge , direkter Weg. Java Basics - Anfänger-Themen 5
G Fibonacci Algorithmus Java Basics - Anfänger-Themen 22
0 Fibonacci Zahlen seeeehr schnell berechnen Java Basics - Anfänger-Themen 9
S Fibonacci Rückrechnung! Java Basics - Anfänger-Themen 5
K Fibonacci Zahlen Java Basics - Anfänger-Themen 2
K Programmieren von den ersten 70 Fibonacci-Zahlen Java Basics - Anfänger-Themen 2
G fibonacci was stimmt an meinem code nicht? Java Basics - Anfänger-Themen 2
S Fibonacci Zahlenvergeich Java Basics - Anfänger-Themen 6
G Iterativer Algorithmus zur Berechnung der Fibonacci Zahlen Java Basics - Anfänger-Themen 1
P Fibonacci-Zahlen Java Basics - Anfänger-Themen 6
S 2 Reihen ratio-btn, eine Reihe funktioniert andere nicht Java Basics - Anfänger-Themen 4
new_to_coding Rekursive Reihe implementieren Java Basics - Anfänger-Themen 1
rosima26 Taylor-Reihe in Java Java Basics - Anfänger-Themen 20
O Erste Schritte ln(1+x) Reihe Programmieren Java Basics - Anfänger-Themen 6
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
K Apache POI Excel Letzte Reihe einer bestimmten Spalte Java Basics - Anfänger-Themen 1
G Rekursives Programmieren --> harmonische Reihe Java Basics - Anfänger-Themen 3
S Gibt es eine Funktion, die gewissermaßen eine Reihe von instanceOf() vereinheitlicht? Java Basics - Anfänger-Themen 19
G harmonische Reihe Java Basics - Anfänger-Themen 2
M Java Anfänger - Video Tutorial Reihe (DEUTSCH) Java Basics - Anfänger-Themen 11
G Mehrere If-else-Sätze der Reihe nach durchlaufen lassen Java Basics - Anfänger-Themen 2
T Harmonische Reihe Java Basics - Anfänger-Themen 5
A Taylor Reihe für Sinus Java Basics - Anfänger-Themen 3
w0ddes Reihe deselektieren in einer JTable Java Basics - Anfänger-Themen 2
B vorletzten Wert aus einer Reihe bekommen Java Basics - Anfänger-Themen 6
Shalimar Längste Reihe anzeigen lassen Java Basics - Anfänger-Themen 11
A Eine Javaaufgabe die ich nicht auf die Reihe bekomme. Java Basics - Anfänger-Themen 7
W Innerhalb TableModel auf aktivierte Reihe reagieren Java Basics - Anfänger-Themen 3
0 Harmonische Reihe rekursiv berechnen? Java Basics - Anfänger-Themen 10
Dilandau erweiterbare reihe aus elementen machen? Java Basics - Anfänger-Themen 10
S Zahlen reihe Programmieren Java Basics - Anfänger-Themen 12
G JTable Reihe und Spalte Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Neue Themen


Oben