Perl Rekursion "Fibonnacci"
 

Hallo,

kann mir jemand erklären, wie das Programm zu dem unten genannten Ergebnis kommt?Ich versteh den Rechenweg nicht.
Also der erste Wert ist klar, ist der Zähler von der Schleife. Aber der zweite Wert, ich versteh nicht wie es zu diesen Zahlen kommt.

---------------------------------------------------------------
sub fibonacci{

my($value)=@_;
return 1 if $value <= 2;
return fibonacci($value -1)+fibonacci($value -2);
}
print "$_: ", fibonacci($_), "\n" for (1 .. 7);

-----------------------------------------------------------------
Die Ausgabe ist folgende:

1: 1
2: 1
3: 2
4: 4
5: 8
6: 16
7: 32

Danke im Vorraus

Komisch, ich kenn fibonacci anders-
-> wikipedia
Die Fibonacci-Folge ist eine unendliche Folge von Zahlen (den Fibonacci-Zahlen), bei der die Summe zweier benachbarter Zahlen die unmittelbar folgende Zahl ergibt: 0, 1, 1, 2, 3, 5, 8, 13, …


Bei deiner Formel ist aber das neue Ergebnis das Quadrat der vorhergehenden Zahl.

Ich denke Mal der Fehler liegt da begraben
return fibonacci($value -1)+fibonacci($value -1);

Eher so
return fibonacci($value -1)+fibonacci($value);

ja also da war ein kleiner Fehler in dem Code hab es korrigiert.
und zwar steht bei uns im Skript folgendes

return fibonacci($value -1)+fibonacci($value -2);

Was ist jetzt eigentlich dein Problem?

Wenn ich deinen Code, wie er im 1. Post steht, ausführe bekomme ich als Ausgabe:
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13

Was der Fibonaccifolge entspricht.
Oder hat sich deine Frage jetzt von selbst beantwortet weil du den Code falsch aus dem S***** abgetippt hast?

Also ich versteh nicht genau wie das Programm auf die fibonacci Zahlen kommt.
Klar ist auch die Ausgabe für den ersten und zweiten Durchlauf.
Was mir Probleme bereitet ist, wenn sich die Funktion immer wieder selbst aufruft wird $value doch immer kleiner, ich dachte das die Funktion sich immer wieder selbst aufruft bis $value = 1 ist und dann ausgegeben wird. Das kann ja aber nicht sein. Kann mir jemand z.B. mal für den 6. Schleifendurchlauf erklären, wie man dauf das Ergebnis 8 kommt, bzw. wie das Programm das rechnet in einzelnen Schritten so das ich es nachvollziehen kann.

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13

Wie wäre es wenn du dir selbst die Mühe machst und damit deine Frage selbst beantwortest?

Nimm Stift und Papier in die Hand oder notier es am besten gleich hier...

also wenn ich es so durch gehe schreibe ich folgendes auf

Zum Beispiel für den Schleifendurchlauf mit 6 es ruft sich doch immer wieder selber auf und $value wird immer niedriger vom Wert:

fibonacci(6-1) + fibonacci(6-2)
fibonnacci(5) + fibonacci(4)

fibonacci(5-1) + fibonacci(4-1)
fibonacci(4) + fibonacci(3)

fibonacci(4-1) + fibonacci(3-1)
fibonacci(3) + fibonacci(2)

fibonnacci(3-1) + fibonnacci(2)= 1
fibonnacci(2)=1 + 1
= 2

Nach meinem Verständnis kann doch immer nur 2 ausgegeben werden? Wo habe ich den Denkfehler?

Dein Fehler ist, dass du denkst, dass nur die letzten zwei aufrufe der Funktion einen Wert zurückgeben, welche addiert und an die printfunktion übergeben werden.
Tatsächlich gibt aber die Funktion den Wert an die Funktion wieder von der sie aufgerufen wurde.

Ich gehs mal mit Aufruf 4 durch ( 6 ist mir zu viel zum schreiben)
fib(4)

fib(4-1) + fib(4-2) [ diese beiden wurden von fib(4) aufgerufen ]

fib(3-1) + fib(3-2) [ diese beiden wurden von fib(4-1) aufgerufen ]
[ fib(4-2) ruft keine Funktion auf sondern gibt den Wert 1 zurück da value<=2 ist ]

[ fib(3-1) ruft keine Funktion auf sondern gibt den Wert 1 zurück da value<=2 ist ]
[ fib(3-2) ruft keine Funktion auf sondern gibt den Wert 1 zurück da value<=2 ist ]

[ da fib(3-1) und fib(3-2) jeweils den Wert 1 an fib(4-1) zurückgeben werden diese in
fib(4-2) aufaddiert zu 2 und dieser Wert zurückgegeben )

[ somit gibt fib(4-2) den Wert 2 an fib(4) zurück und fib(4-2) gibt den Wert 1 an fib(4)
zurück. beide Werte werden in fib(4) aufaddiert zu 3 und zurückgeben an die
printfunktion. ]

[ print erhält den Wert 3 und gibt diesen auf ]


So in etwa sollte das ganze aussehen.

Nimm mal wirklich Stift und Papier in die Hand und rechne Zeile für Zeile!
Entweder warst du faul oder extrem unkonzentriert und kommst daher auf die total falsche Lösung.

Also: Konzentrier dich, schreib auf...dann findest Du auch die Lösung!

ahh ich glaube ich habe es verstanden. Es entstehen immer wieder neue "Verzweigungen, welche eine 1 zurückliefern, umso höher die Eingabe-->umso mehr verzweigungen....vielen Dank für eure Hilfe, spezieller dank geht an Zerafir!!