# Rekursion Fibonacci



## cyboern (25. Jan 2011)

```
public class Fibonacci{
    public static int fib(int n){
    // requires n >= 0
    System.out.println("call fib(" + n + ")"); //Protokollierung
   if (n==0) return 0;
   if (n==1) return 1;
      return (fib(n-1)+fib(n-2));
}
public static void main(String[] arg){
   int n;
   System.out.println("gib ganze Zahl >= 0:");
   n = SavitchIn.readLineInt();
   System.out.println("Ergebnis: fib(" + n + ") = "
   + fib(n)); //Aufruf
}
}
```

Also ich gebe die Zahl 4 ein!

dann wird oben das unterporgramm fib mit 4 durchlaufen und "call fib(4)" ausgegeben
dann kommt man zu der stelle return (fib(n-1)+fib(n-2));

hier wird das ganze dann mit 4-1 aufgerufen, also 3

es wird wieder call fib(3) ausgegeben (die stelle +fib(n-2)); wird gar nicht durchlaufen oder ???
dann eben ausgabe  "call fib(3)" 
 "call fib(2)"
 "call fib(1)"

dann wenn das ganze mit 1 durchaufen wird sollte doch mit "return 1" das programm abgebrochen werden oder ??
wenn ich debugge dann wird return 1 durchlaufen aber er springt nicht aus der methode raus??
also wird nochmal das durchgeführt... return (fib(n-1)+fib(n-2));

und wieso werden die zahlen dann wieder höher
wenn ich das programm ausführe  kommt folgende ausgabe

wäre echt sehr nett mit einige tipps zu geben !


4
call fib(4)
call fib(3)
call fib(2)
call fib(1)
call fib(0)
call fib(1)
call fib(2)
call fib(1)
call fib(0)
Ergebnis: fib(4) = 3


----------



## Gonzo17 (25. Jan 2011)

Du musst den Code wirklich Zeile für Zeile durchlaufen.

Es ist klar, dass fib(n-1) solange aufgerufen wird:

call fib(4)
call fib(3)
call fib(2)
call fib(1)

An dieser Stelle allerdings, bei n=1, haben wir ein Abbruchkriterium erfüllt! Danach wird "zurückgesprungen" zum letzt höheren Rekursionsschritt und dieser wird abgeschlossen. Und zwar wird dort (n=2) fib(n-2) aufgerufen. Somit landen wir hier:

call fib(0)

Wieder ein Abbruchkriterium, es wird 0 zurückgegeben. Also wieder nen Schritt zurück, wir sind bei n=3 und es wird abermals fib(n-2) aufgerufen.

call fib(1)

Auch hier, das Abbruchkriterium ist erfüllt. Das ganze also nochmal, bei n=4 eben gleiche fib(n-2) wird aufgerufen.

call fib(2)

Hier sind wir nun und da gibts kein Abbruchkriterium, deswegen wird fib(n-1) aufgerufen!

call fib(1)

Wieder das gleiche Spiel, Abbruchkriterium greift, in den Methodenaufruf zuvor springen und fib(n-2):

call fib(0)

Jetzt sind wir am Ende, denn hier greift zum letzten mal ein Abbruchkriterium, alle weiteren Schritte "nach oben" zählen "nur noch" die Ergebnisse zusammen.


----------



## SlaterB (25. Jan 2011)

der zweite Wert vom Plus wird auch immer aufgerufen, nur eben später
folgender Baum zweigt, was alles aufgerufen wird (die 4 ganz oben setzt sich aus 3 und 2 darunter zusammen),
davor die Zahl zeigt die Reihenfolge, was wann drankommt

```
1: 4

                 2: 3                               7: 2

     3: 2               6: 1                  8: 1           9: 0

4: 1     5: 0
```


----------



## cyboern (25. Jan 2011)

ok thx für die schnellen antworten, echt super!!

was ich jetzt noch nicht verstehe wie das ergebnis ergebnis "3" entsteht?

lg


----------



## SlaterB (25. Jan 2011)

einfach alles addieren, wie mein Baum zeigt kommt letztlich 3x fib(1) und 2x fib(0) in die Gesamtsumme (alle Blätter),
was ist fib(1), was ist fib(0), eingesetzt, zählen, fertig


----------



## Gonzo17 (25. Jan 2011)

Naja, so sind eben auch die Fibonacci-Zahlen definiert. Kannst ja mal auf Wikipedia schauen: Fibonacci-Folge ? Wikipedia


----------



## cyboern (25. Jan 2011)

ok das ganze ist noch etwas schwierig für mich... aber geht schön langsam

im nächsten beispiel:

```
public static void myst(int n){
if (n<=0) 
   System.out.println("B");
else {
   System.out.println("R");
   myst(n-1);
   myst(n+1);}
}
```

man führt das ganze mit myst(1) aus:

1 wird in 0&2 geteilt

2 wird in 1&3 geiteilt

1 wird in 0&2 geteilt
3 wird in 2&4 geteilt

usw...

das heisst es wird immer RBRBRBRB ausgegeben bis n einmal zu groß für den speicherbereich Integer wird und dann abbricht ??

richtig ??

glg


----------



## SlaterB (25. Jan 2011)

ob RBRBRBRB rauskommt oder nicht kannst du doch allein dadurch feststellen, indem du es laufen läßt,

vorher im Kopf zu überlegen wie es sein wird, ist ne gute Idee, aber die erste Überprüfung + Korrektur-Überlegung kannst du doch ohne Forum durchführen,
wenn du das tatäschliche Ergebnis (nicht RBRBRBRB ..) dann nicht verstehst notfalls fragen..


----------



## ARadauer (25. Jan 2011)

> das heisst es wird immer RBRBRBRB ausgegeben bis n einmal zu groß für den speicherbereich Integer wird und dann abbricht ??


nein... wieso?


----------



## ARadauer (25. Jan 2011)

ok start mit 4

```
in myst mit 4 ausgabe R aufruf -1
   in myst3 ausgabe R aufruf -1
      in myst 2 ausgabe R aufruf -1
         in myst 2 ausgabe R aufruf -1
            in myst 1 ausgabe R aufruf -1
              in myst 0 ausgabe R fertig
            wir sind wieder in myst 1 aufruf +1
            in myst 2 ausgabe R aufruf -1

usw...
```

mah... ich hätte da schöne leerzeich


----------



## SlaterB (25. Jan 2011)

> in myst 0 ausgabe R fertig
auch nicht hilfreich


----------



## cyboern (25. Jan 2011)

das heisst das ganze wird von oben nach unten und dann wieder von unten nach oben durchlaufen??
ich glaub ich verstehs doch nicht nicht,

der baum da beim den finocci zahlen war logisch...

"in myst 0 ausgabe R fertig" sollte doch B kommen oder ??

lg


----------



## SlaterB (25. Jan 2011)

es ist immer noch ein Baum, nur unendlich, 
mal wieder von 1 aus gesehen statt 4:

```
1: 1
2: 0                3: 2
           4: 1             3 (kommt nie dran)
5: 0                6: 2
           7: 1             3 (kommt nie dran)
8: 0                9: 2
```
usw.


----------



## ARadauer (25. Jan 2011)

cyboern hat gesagt.:


> das heisst das ganze wird von oben nach unten und dann wieder von unten


nein es läuft einfach weiter...

schau dir das an...

```
public class Rekursion {
   
   public static void main(String[] args) {
      rec(5);
   }
   
   public static void rec(int i){
      System.out.println(i+ " im aufruf ");
      if(i<0)
         return;
         
      System.out.println(i+" vor der methode");
      rec(i-1);
      System.out.println(i+" nach der methode");
   }

}
```
wenn du jetzt eine methode drinnen bist und diese ist fertig. läuft es an der stelle wo du sie aufgerufen hast weiter...


----------



## cyboern (25. Jan 2011)

@slater
wenn ich jetzt vinocci mit 6 aufrufe dann sieht das so aus oder ??

```
1:  6

                                    2: 5                              16:4
                
                           3:  4       11: 3                  17:3        18: 2

                 4: 3         8: 2   12:2  13:1       21: 2      22: 1     19:1     20: 0

      5:  2         9:1  10:1  14:1  15:0       23:1       24:0    

6: 1     7:0
```


----------



## SlaterB (25. Jan 2011)

vinocci = Fibonacci?

die Reihenfolge ist falsch, bis 8 stimmt es noch, 
als nächstes kommt dann aber die 2 von einer Stufe höher, nicht die 3 von zwei Stufen höher

'11' hast du doppelt

wieso kommt 15, 16, 17 ganz rechts vor dem linken Teilbaum dort mit 18-21?
es muss doch ein Konzept geben, etwa immer links vor rechts


----------



## cyboern (25. Jan 2011)

ja sry ich habs falsch hingeschrieben, aber eigentlich richtig gedacht,
und auf der rechten seite werden auf die bäume von rechts aussen nach innen abgearbeitet ?!?


----------



## SlaterB (25. Jan 2011)

nö, siehe auch edit im vorherigen Post


----------



## cyboern (25. Jan 2011)

jetzt stimtms oda ?


----------



## SlaterB (25. Jan 2011)

mal schauen



SlaterB hat gesagt.:


> die Reihenfolge ist falsch, bis 8 stimmt es noch,
> als nächstes kommt dann aber die 2 von einer Stufe höher, nicht die 3 von zwei Stufen höher


ist quasi noch drin, jetzt sogar nur noch bis 7 richtig, danach 8 zwei Stufen höher als 9 nur eine Stufe höher, 
wobei (8:2) auch gar nicht Nachfolger 1 und 0 hat falls ich den Baum richtig lese, da ist irgendwas kaputt



> '11' hast du doppelt


scheint nicht mehr so zu sein, gut



> wieso kommt 15, 16, 17 ganz rechts vor dem linken Teilbaum dort mit 18-21?
> es muss doch ein Konzept geben, etwa immer links vor rechts


jetzt zwar andere Zahlen, aber das ist doch immer noch nahezu gleich vorhanden?!

was ist dein Konzept?
am Baum ist das doch nicht mal mehr Denken sondern so systematisch wie mit einem Bleistift durch ein Labyrinth,
als Regeln gibt es im Grunde nur:
"erst linken Nachfolger, wenn es nicht mehr weitergeht dann eine Stufe höher und rechten Nachfolger falls vorhanden (dort natürlich wieder links bevorzugen)"


----------



## cyboern (25. Jan 2011)

so ich versuchs nochmal



                                                     1:  6


                                      2: 5                              17:4


                           3:  4          12: 3                         18:3               19: 2


                 4: 3        9: 2          13:2       14:1         22: 2      23: 1     20:1     21: 0


      5:  2      8:1   10:1    11:1   15:1   16:0                   24:1  25:0      


6: 1     7:0


----------



## cyboern (25. Jan 2011)

so ich versuchs nochmal



```
1:  6


                                      2: 5                              17:4
                

                           3:  4          12: 3                         18:3               19: 2


                 4: 3        9: 2          13:2       14:1         22: 2      23: 1     20:1     21: 0


      5:  2      8:1   10:1    11:1   15:1   16:0                   24:1  25:0      


6: 1     7:0
```

hab jetzt mal die schlampigkeitsfehler raus gemacht,

beim rechten beim wird von oben nach unten von aussen nach innen und zuerst das linke dann das rechte durchlaufen ??

so würde sich das ganze auch mit der ausgabe meines programmes decken


----------



## cyboern (25. Jan 2011)

nein irgendwas passt das beim rechten baum noch nicht

call fib(4)
call fib(3)
call fib(2)
call fib(1)
call fib(0)
call fib(1)
call fib(2)
call fib(1)
call fib(0)


----------



## SlaterB (25. Jan 2011)

schau dir deinen linken Teilbaum an, auf 2: 5 folgt links 3: 4 und rechts erst 12: 3,
bis der rechte Unterteilbaum von 2: 5 drankommt wird der linke also komplett abgearbeitet,
soweit korrekt nach den Regel,

und was machst du rechts? hälst dich einfach wieder nicht daran,
auf 17: 4 folgt bei dir links 18: 3 und rechts 19: 2, obwohl doch erst 18:3 komplett durchlaufen werden muss bevor es mit dem rechten Nachfolger von 17: 4 weitergeht,
die 19 ist der linke Nachfolger der 18 usw.


(links ist bei 13, 14, 15, auch ein Fehler, fällt nicht auf bei beides eine 1 ist)

---

man kann Postings auch editieren..


----------



## cyboern (25. Jan 2011)

```
1:  6


                                      2: 5                              17:4
                

                           3:  4          12: 3                         18:3               23: 2


                 4: 3        9: 2          13:2       14:1         19: 2      22: 1     24:1     25: 0


      5:  2      8:1   10:1    11:1   15:1   16:0            20:1  21:0      


6: 1     7:0
```


THIS IS IT =)!!
vielen vielen dank


----------



## SlaterB (25. Jan 2011)

13-16 nochmal überdenken, dann ist gut


----------



## cyboern (25. Jan 2011)

cyboern hat gesagt.:


> ```
> 1:  6
> 
> 
> ...


----------



## cyboern (25. Jan 2011)

jetzt kapier ich auch das andere beispiel:

ist das dann quasi eine programm das nie abbricht ??

weil wenn man da auch so vorgeht dann wird immer aus 2->1&3 wobei er zum 3er nie kommt und wieder aus 1wird 0&2 uws uws uws...


----------



## SlaterB (25. Jan 2011)

9 hat mit 10 und 11 je 1 als Nachfolger fällt mir verspätet auch noch auf, tralala

> ist das dann quasi eine programm das nie abbricht ??
ja, mal abgesehen von StackTraceException,
testen?!


----------



## cyboern (25. Jan 2011)

ja wenn ich es in eclipe durchlaufen lasse dann kommt eben irgend so eine komische fehlermeldung(stack overflop error

ich lerne gerade auf einen test, bin leider noch nicht so gut drauf in die richtung !!


----------



## Gonzo17 (25. Jan 2011)

SlaterB hat gesagt.:


> 9 hat mit 10 und 11 je 1 als Nachfolger fällt mir verspätet auch noch auf, tralala


11:0 muss es doch heißen, oder?


----------



## SlaterB (25. Jan 2011)

gewiss


----------

