Fibonacci - Rekursion [Programmieren]

...komplette Frage anzeigen

8 Antworten

Das ist ja das schöne an der Rekursion: Das Programm behält die Kontrolle! Es zerlegt das Argument der Funktion fibo so lange rekursiv, bis es eine Abbruchbedingung für die aktuelle Rekursionsebene erreicht. Die ist immer dann gegeben, wenn das Argument 1 oder 2 ist. Das Programm liefert dann den jeweiligen Wert, also 0 oder 1 und kehrt in die vorherige Rekursionsstufe zurück. Dort addiert es die gefundenen Werte und setzt mit der nächsten fibo ( x ) - Anweisung fort. Auch diese wird rekursiv zerlegt usw. Am Ende hat das Programm sämtliche fibo-Aufrufe in bestimmte Werte (entweder 0 oder 1) umgewandelt und alle diese Werte addiert. Dann wird das Ergebnis ausgegeben.

fibo ( 5 ) wird z.B. so abgearbeitet:

fibo ( 5 ) = fibo ( 4 ) + fibo ( 3 )

[nun wird zunächst fibo ( 4 ) weiter zerlegt, fibo ( 3 ) bleibt erst mal so stehen:]

= fibo ( 3 ) + fibo ( 2 ) + fibo ( 3 )

[nächste Rekursion: fibo ( 3 ) wird weiter zerlegt, der Rest bleibt stehen:]

= fibo ( 2 ) + fibo ( 1 ) + fibo ( 2 ) + fibo ( 3 )

[für fibo ( 2 ) ermittelt das Programm den Wert 1 Damit ist diese Rekursion beendet und es geht zurück in die vorherige Rekursionsebene. Dort wird nun fibo ( 1 ) bearbeitet:]

= 1 + fibo ( 1) + fibo ( 2) + fibo ( 3 )

[für fibo ( 1 ) ermittelt das Programm den Wert 0. Damit ist auch diese Rekursion beendet und es geht zurück in die vorherige Rekursionsebene. Dort wird nun der ermittelte Wert 0 zu dem bereits vorher ermittelten Wert 1 addiert und mit fibo ( 2 ) fortgesetzt: ]

= 1 + 0 + fibo ( 2 ) + fibo ( 3 )

= 1 + fibo ( 2 ) + fibo ( 3 )

[für fibo ( 2 ) ermittelt das Programm wieder den Wert 1. Damit ist auch diese Rekursion beendet und es geht zurück in die vorherige Rekursionsebene. Dort wird nun der ermittelte Wert 1 zu der bisher bereits ermittelten Summe 1 addiert und mit fibo ( 3 ) fortgesetzt: ]

= 1 + 1 + fibo ( 3 )

= 2 + fibo ( 3 )

= 2 + fibo ( 2 ) + fibo ( 1 )

[für fibo ( 2 ) ermittelt das Programm wieder den Wert 1. Damit ist auch diese Rekursion beendet und es geht zurück in die vorherige Rekursionsebene. Dort wird nun der ermittelte Wert 1 zu der bisher bereits ermittelten Summe 2 addiert und mit fibo ( 1 ) fortgesetzt: ]

= 2 + 1 + fibo ( 1)

= 3 + fibo ( 1 )

[für fibo ( 1 ) ermittelt das Programm wieder den Wert 0. Damit ist auch diese Rekursion beendet und es geht zurück in die vorherige Rekursionsebene. Dort wird nun der ermittelte Wert 0 zu der bereits vorher ermittelten Summe 3 addiert: ]

= 3 + 0

= 3

Damit sind alle Rekursionen erledigt und das Programm gibt den Wert 3 aus. Und das ist gerade der Wert der fünften Fibonacci-Zahl.

Herzlichen Dank! Hat mir wirklich sehr geholfen.

0

§1: Man sagt zwar "1. Fib...", aber deine beiden Startwerte entsprechen nicht der "Standard Fibonacci-Funktion" (OEIS A000045 um 1 verschoben):
Fibonacci(0)=0 und Fibonacci(1)=1

§2: zu "Woher weiß das Programm, dass an der 5. Stelle..."
Das ist es ja gerade, dass die rekursive Funktion das nicht weiß, sondern die Aufgabe hat:
"Frage Deine beiden Vorgänger und gib die Summe beider zurück".
Mit jedem neuen Funktionsaufruf legt der PC intern neue lokale Variablen an -> dabei wird immer mehr Speicher verbraucht (lese bei Wiki Stackpointer/Stapelspeicher)
Nur bei Argument 0 oder 1 wird einfach das SELBE zurückgegeben und der Speicher wieder abgebaut. Viele Sprachen haben eine Begrenzung: Rekursionstiefe!! (Browser um 900)

§3: Es gibt 3 weitere Algorithmen für Fibonacci -> unter
http://www.gerdlamprecht.de/Roemisch_JAVA.htm Beispiele 7 und 8
Mit der expliziten Formel kann man beim Umkehrfunktionen Rechner komplexe Zahlen und sehr große Zahlen berechnen: Fibonacci(-0.3-0.4i) oder Fibonacci(999999999)

Fib(x) - (Mathematik, programmieren, Fibonacci)

Noch eine kleine Ergänzung zu dem bereits Gesagten:

http://rosettacode.org/wiki/Fibonacci_sequence

Da ist die Fibonacci-Reihe in allen möglichen Sprachen implementiert. FMS Logo ist nicht dabei, davon hab ich aber auch noch nie was gehört; wenn du Beispielcode erwartest, solltest du vielleicht auf eine verbreitetere Sprache umsteigen. Aber auf jeden Fall sollte das Prinzip auf der Seite doch ganz gut vermittelt werden; irgendeine Sprache wirst du ja hoffentlich verstehen.

Mit ein paar Schreibbefehlen kann man das Programm selbst sagen lassen, was es tut.

Hier zeige ich, wie das in JavaScript geht. (Den Code unter dem Dateinamen fibo.html abspeichern und mit dem Browser öffnen.) Die Funktion fibo sagt in rot, mit welchem Argument sie gerade aufgerufen wurde, und in blau sagt sie, welches Resultat sie gerade zurückgibt. So läßt sich der Weg, auf dem das Endergebnis entsteht, mitverfolgen.

<html>
<meta charset="iso-8859-1">
<style>
.r{color:indianred;}
.b{color:royalblue;}
p{padding:0.5em; border:solid thin silver;}
</style>
<script>
function fibo(n){
    document.write("<span class=\"r\">" + n + "</span> ");
    var res;
    if (n<=1){
        res = 0;
    }
    else if (n==2){
        res = 1;
    }
    else{
        res = fibo(n-2)+fibo(n-1);
    }
    document.write("<span class=\"b\">" + n + "</span> ");
    return res;
}

for(var i=1; i<=16; i++){
    document.write("<p>\n");
    document.write("Berechne fibo(" + i + ")<br>\n");
    var f = fibo(i);
    document.write("<br>\nDas Ergebnis ist " + f + "</p>\n");
}

</script>
</html>

Noch etwas wird dabei deutlich sichtbar: Wenn man so etwas wie die Fibonacci-Funktion berechnen will, ist diese naiv angewandte Rekursion so ziemlich die ungeeignetste Methode dafür. Der Algorithmus verbringt fast die ganze Zeit damit, das, was er schon längst berechnet hat, wieder und wieder zu berechnen. Daß man in den Lehrbüchern und Tutorials, wo die Rekursion erklärt wird, so oft den Fibonacci findet, sollte also nicht mißverstanden werden. Es dient wirklich nur der Demonstration und ist nicht die Methode, die man in der Praxis dafür verwenden würde.

Mir ist beim Editieren ein Fehler passiert, sorry.

Damit man sieht, was abgeht, muß das Ende der Funktion fibo(n) so lauten, es wird res angezeigt:

    document.write("<span class=\"b\">" + res + "</span> ");
    return res;
}
0

http://perlgeek.de/de/artikel/rekursion

kann dir vielleicht zum Thema wie Rekursion funktioniert helfen. Die nutzen da zwar C statt diesem komischen FMS Logo, aber es sollte verständlich sein. Vorallem der Text dazu...

*ich komme mit der Fibonacci-Reihe nicht wirklich zurecht. und 5-2=3 ... Tut mir leid, es haben sich ein paar Fehler eingeschlichen.

Weil 5 - 2 = 3 und nicht 2 ist? Kommt denn bei 5 Durchläufen "1 2 3 5 8" raus? Funktioniert es nicht, oder verstehst du es nur nicht?^^

Ups, tut mir leid.. Komme aber mit dem richtigen Wert auch nicht viel weiter. Es kommt: "0 1 1 2 3" raus? Ich versteh es nicht.

0
@Tiina234

1-1-2-3 ist ja schonmal der richtige Beginn, die Formel stimmt schon.

0
@nex4k

Nunja, das Programm hab leider nicht ich geschrieben. Die Lösung war bei den Übungsaufgaben dabei. Ich verstehe nur den Zusammenhang nicht.. also wie das Programm dann auf die Zahlen kommt. Wie ich es verstehe, dann müsste immer die Zahl 1 oder 0 herauskommen, was ja dann überhaupt nichts mit der Zahlenreihe zu tun hat? Bisher hatte ich immer nur Aufgaben, wo das Programm sich in einer Zeile nur 1x selbst aufruft und nicht wie hier 2x.

0
@Tiina234

Nein, da ist noch ein dritter Block, der ausgeführt wird wenn n=0 oder n=1 nicht zutreffen:

((fibo (:n-1))+(fibo(:n-2)))

Für n=3 beispielsweise kommt dieser dritte Fall zum Tragen und am Ende steht dann da = fibo(3-1) + fibo(3-2) --> fibo(2) + fibo(1). Beides muss aber erst wieder berechnet werden, indem sich die Funktion selbst neu mit anderen Argumenten aufruft (also anderem n) für n=2 und n=1. Bei fibo(1) tritt der zweite Fall ein und es kommt sofort 1 zurück. Bei fibo(2) dagegen tritt mal wieder der dritte Fall ein (-> fibo(1) + fibo(0) ) wobei diese zwei Dinge wieder durch Rekursion, das sich-selbst-aufrufen, berechnet werden.

0
@nex4k

Ok vielen Dank! Ich dachte, bei fibo (1), wird der Wert 0 zurückgegeben? Wegen if :n = 1 [op 0]? und bei fibo (2) der Wert 1, wegen: if :n = 2 [op 1]. Dann würde fibo (1) zu 0 und fibo (2) zu 1 werden -> 0 + 1 -> also "n = 1 -> wenn :n = 1 [op 0] ? So dachte ich zu Beginn! Ich hätte noch eine kurze Frage, wenn es in Ordnung geht: Wie wäre es denn, wenn für :n die Zahl 5 eingegeben wird?

0
@Tiina234

Ja, bei n=1 kommt 0. Habe ich in der Eile verwechselt.

Bei n=5 hast du auf der ersten Ebene fibo(4)+fibo(3). Fibo(4) löst sich wiederum in fibo(3)+fibo(2) auf, fibo(3) in fibo(2)+fibo(1); ...

0

Vielen Dank an alle für die große Hilfe! Mfg

Was möchtest Du wissen?