Rekursive Funktionen – Die Fibonacci-Folge

Du kennst vielleicht schon Schleifen in der Programmierung, aber rekursive Funktionen funktionieren völlig anders. Hier ruft sich eine Funktion immer wieder selbst auf, bis ein bestimmtes Ergebnis erreicht ist.

Die Fibonacci-Folge ist das klassische Beispiel für Rekursion. Jede Zahl entsteht durch Addition der beiden vorherigen Zahlen – ein Prinzip, das sich perfekt für rekursive Programmierung eignet.

Merke dir: Bei Rekursion löst eine Funktion ein Problem, indem sie sich selbst mit einem kleineren Problem aufruft!

Gliederung

Wir schauen uns an, wie rekursive Funktionen grundsätzlich arbeiten und warum die Fibonacci-Folge so besonders ist. Du lernst die mathematischen Eigenschaften kennen und verstehst, wie man das Ganze programmiert.

Außerdem erfährst du, welche Komplexität solche Algorithmen haben. Das ist wichtig, weil rekursive Funktionen manchmal sehr langsam werden können.

Am Ende vergleichen wir die Fibonacci-Rekursion mit anderen rekursiven Algorithmen. So bekommst du ein Gefühl dafür, wann Rekursion sinnvoll ist und wann nicht.

Tipp: Die Gliederung zeigt dir, dass wir vom Grundprinzip zur praktischen Anwendung gehen!

Gliederung (Fortsetzung)

Im zweiten Teil geht es um die praktischen Aspekte. Du lernst verschiedene Rekursionsarten kennen und kannst die Fibonacci-Folge richtig einordnen.

Besonders wichtig ist das Laufzeitverhalten – hier merkst du schnell, warum manche rekursive Algorithmen problematisch werden können. Die Fibonacci-Rekursion ist nämlich ziemlich ineffizient!

Der Vergleich mit anderen rekursiven Algorithmen hilft dir zu verstehen, wann Rekursion eine gute Wahl ist. Nicht immer ist die eleganteste Lösung auch die beste.

Wichtig: Komplexität und Laufzeit sind entscheidend für die Bewertung von Algorithmen!

Eigenschaften rekursiver Funktionen

Rekursion kommt vom lateinischen "recurrere" (zurücklaufen) – und das beschreibt perfekt, was passiert. Eine Funktion läuft immer wieder zu sich selbst zurück, bis das Problem gelöst ist.

Im Prinzip ist Rekursion ein unendlicher Vorgang. Die Funktion definiert sich mithilfe von sich selbst – das klingt erstmal verrückt, funktioniert aber super! Eine relativ kurze Anweisung kann so komplexe Probleme lösen.

Das Besondere: Jeder Teilvorgang hängt vom vorherigen ab. Zwischen allen Objekten besteht eine rekursive Beziehung – wie bei den Fibonacci-Zahlen, wo jede Zahl von den beiden vorherigen abhängt.

Cool: Mit nur wenigen Zeilen Code kannst du komplexe Probleme lösen!

Eigenschaften rekursiver Funktionen (Fortsetzung)

In der Programmierung ist Rekursion eigentlich ganz einfach: Eine Funktion ruft sich selbst auf. Das war's! Aber Vorsicht – ohne Stopp-Regel läuft das Programm unendlich weiter.

Deshalb brauchst du immer eine Abbruchbedingung (auch Basisfall genannt). Rekursion arbeitet nach der Top-Down-Methode – du zerlegst das große Problem in immer kleinere Teilprobleme.

Jeder rekursive Aufruf sollte mit einer kleineren Instanz des gleichen Problems arbeiten. So kommst du irgendwann beim Basisfall an, der ohne weitere Rekursion gelöst werden kann.

Regel: Ohne Abbruchbedingung = Endlosschleife = Absturz!

Funktionsprinzip der Fibonacci-Folge

Die Fibonacci-Folge ist eine unendliche Zahlenreihe mit einer einfachen Regel: Jede Zahl entsteht durch Addition der beiden vorherigen Zahlen. Das sieht so aus: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Die Berechnung ist simpel: 1+1=2, 1+2=3, 2+3=5, 3+5=8 und so weiter. Mathematisch schreibt man das als rekursive Formel: aₙ = aₙ₋₁ + aₙ₋₂, mit a₁ = a₂ = 1.

Diese Formel ist perfekt für rekursive Programmierung! Um die n-te Fibonacci-Zahl zu berechnen, rufst du die Funktion einfach für die beiden vorherigen Zahlen auf.

Genial: Eine so einfache Regel erzeugt eine der berühmtesten Zahlenfolgen der Mathematik!

Eigenschaften der Fibonacci-Zahlen

Fibonacci-Zahlen bestehen nur aus natürlichen Zahlen und haben einen festen Anfang (1, 1). Die Folge ist unendlich, aber ihr Verhalten ist vorhersagbar und faszinierend.

Das Coolste: Das Verhältnis zweier aufeinanderfolgender Zahlen nähert sich dem Goldenen Schnitt an! Der Goldene Schnitt teilt eine Strecke so, dass das Verhältnis der Gesamtstrecke zum größeren Teil dem Verhältnis des größeren zum kleineren Teil entspricht.

Je weiter du in der Fibonacci-Folge fortschreitest, desto näher kommt der Quotient aufeinanderfolgender Zahlen an diesen besonderen Wert heran. Das zeigt, wie Mathematik und Natur zusammenhängen!

Faszinierend: Die Fibonacci-Folge verbindet Informatik, Mathematik und Naturwissenschaften!

Die Entdeckung der Folge

Die Folge ist nach dem italienischen Forscher Leonardo da Pisa (1170-1240) benannt, der unter dem Namen Fibonacci bekannt wurde. Aber eigentlich wurde sie schon viel früher entdeckt!

Im alten Indien und in der Antike nutzten Menschen diese Zahlenfolge bereits, um Wachstum in der Natur zu beschreiben. Fibonacci machte sie aber in Europa bekannt, als er das Wachstum von Kaninchenpopulationen untersuchte.

Seine Arbeit zeigt, wie mathematische Modelle reale Probleme lösen können. Die Fibonacci-Folge beschreibt nicht nur Kaninchen, sondern auch das Wachstum von Pflanzen, Muscheln und vielen anderen Naturphänomenen.

Interessant: Manchmal werden alte Entdeckungen nach den Personen benannt, die sie bekannt gemacht haben!

Wachstum der Kaninchenpopulation

Fibonaccis Kaninchen-Problem ist ein klassisches Beispiel: Ein Paar lebt in einem abgeschlossenen Raum. Im ersten Monat bleibt es allein, im zweiten Monat bekommt es Nachwuchs.

Die Regeln sind simpel: Jedes neugeborene Paar braucht zwei Monate, bis es selbst Nachwuchs bekommt. Dann wirft jedes geschlechtsreife Paar jeden Monat ein neues Paar.

So entwickelt sich die Population: 1. Monat = 1 Paar, 2. Monat = 1 Paar, 3. Monat = 2 Paare, 4. Monat = 3 Paare, 5. Monat = 5 Paare... Genau die Fibonacci-Folge!

Aha-Moment: Ein einfaches biologisches Problem führt zu einem wichtigen mathematischen Konzept!

Grafische Darstellung

Die mathematische Formel der Fibonacci-Folge lautet: F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂. Diese rekursive Definition ist perfekt für die Programmierung geeignet.

Die Zahlenreihe 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... zeigt das exponentiell ansteigende Wachstum. Jede Zahl wird durch die Addition der beiden vorherigen berechnet.

In der grafischen Darstellung siehst du, wie elegant die rekursive Struktur ist. Jeder Wert hängt von den beiden vorherigen ab – ein perfektes Beispiel für rekursive Abhängigkeiten in der Informatik.

Merksatz: Die einfache Formel Fₙ = Fₙ₋₁ + Fₙ₋₂ ist die Basis für rekursive Fibonacci-Programme!