Denkfehler Rekursion

[James15225]

Mein Problem ist, dass ich die Rekursion bei den Fibonacci Zahlen nicht verstehe. Also der Code wäre ja:

public static long fib(int n) {
   if(n == 0) {
     return 0;
   } else if (n == 1) {
     return 1;
   } else {
      return fib(n-1) + fib(n-2);
   }
}

Jetzt verstehe ich aber nicht, wie der Computer rechnet. Die sechste Fibonacci Zahl ist 8. Doch eigentlich müsste der Computer ja 5+4 rechnen und sich dann immer neu aufrufen. Also: 7+6+6+5+5+4+4+3+3+2+2+1+1+0. Also insgesamt: 49. Trotzdem kommt als Ergebnis 8 heraus. Wie rechnet der PC das? Wo ist mein Denkfehler? Und steigt der PC nach dem Return wieder am Anfang der Methode ein, oder an der selben Stelle, an der er auch ausgestiegen ist?

 

[CodeGirl]

Hi du,

der Aufruf von fib(2) ruft zb. fib(2-1)+fib(2-2) auf.
fib(2-1) liefert dabei 1, fib(2-2) liefert 0. Es wird also 1+0 = 1 gerechnet.

Für fib(3) wird fib(2) und fib(1) aufgerufen. Das heisst es werden die Ergebnisse der beiden Aufrufe wieder addiert, also 1+1=2.

Für fib(4) wird dann fib(3) mit fib(2) addiert, also 2+1 =3.

Ich hoffe das hilft dir,
lg

 

[James15225]

Also ist folgende Rechnung richtig: fib(3) würde fib(2) und fib(1) liefern. fib(1) würde dann 1 zurückgeben und fib(2) würde fib(1) und fib(0) liefern. fib(1) würde dann ebenfalls 1 zurückgeben und fib(0)=0, aber dann hätte ich ja 1+1+0, also 2.

 

[CodeGirl]

fib(0) = 0
fib(1) = 1
fib(2) = fib(1)+ fib(0) = 1+0=1
fib(3) = fib(2)+ fib(1) = 1+1=2
fib(4) = fib(3)+ fib(2) = 2+1=3, da (1+1)+(1+0)

Du musst die Ergebnisse eigentlich nur einsetzen, oder eben die Formel, die zum Ergebnis führt...

 

[James15225]

Vielen Dank. Ich hab es endlich verstanden. Bei fib(5) hätte man quasi: fib(4)=fib(3)+fib(2)=fib(2)+fib(1)+fib(1)+fib(0)=fib(1)+fib(0)+fib(1)+fib(1)+fib(0)=3
und
fib(3)=fib(2)+fib(1)=fib(1)+fib(0)+fib(1)=2
Also insgesamt 5
Es wird also immer so lange reduziert bis überall fib(1) oder fib(0) steht und dann addiert.

 

[CodeGirl]

Genau, nun hast du es
lg