fibonacci rekursiv

[ahnungsloser]

Hallo,
ich hab mal noch ne neue Frage. Also, ich hab eine Funktion geschrieben, die die Fibonaccizahlen rekursiv berechnet. Der Quelltext stimmt und die Ergebnisse auch...nur wenn ich jetzt versuche die Werte selbst in einem Schreibtischtest zu errechnen, merke ich, dass ich den Ablauf irgendwie nicht verstanden habe...

Delphi-Quellcode:

function fibo(x:integer):integer;
 begin
  if x < 2 then result := 1
      else result := fibo(x-1) + fibo(x-2)
   end;

Wenn ich jetzt 5 eingebe rechnet die Funktion dann
(5-1)+(4-2)
(4-1)+(3-2) oder wie funktioniert das???

Es wäre toll, wenn mir jemand helfen könnte!!
Danke

[marabu]

Hallo,

vielleicht wird es dir etwas klarer, wenn du dir die folgende Tabelle anschaust. Zuerst habe ich die Substitutionsgleichungen auf der linken Seite von oben nach unten hingeschrieben. Dann habe ich die eckigen Klammerausdrücke von unten nach oben ergänzt. Auf diese Weise löse ich die Rekursion schrittweise auf:

Code:

F(5) = F(4) + F(3)    [5 per Substitution]
F(4) = F(3) + F(2)    [3 per Substitution]
F(3) = F(2) + F(1)    [2 per Substitution]
F(2) = F(1) + F(0)    [1 per Substitution]
F(1) = 1              [1 per Definition] 
F(0) = 0              [0 per Definition]

Grüße vom marabu

[zecke]

Der Link zu Wikipedia

Finde das recht anschaulich beschrieben