4-Fibonacci und Rekursion

Fibonacci und Rekursion

Fibonacci Zahl

📘 Was ist die Fibonacci-Zahl bzw. -Reihe?

Die Fibonacci-Reihe ist eine unendliche Folge von Zahlen, bei der jede Zahl die Summe der zwei vorhergehenden Zahlen ist.

• Die Reihe beginnt mit 0 und 1.
• Danach wird jede neue Zahl durch die Addition der letzten beiden Zahlen berechnet.

Die ersten Berechnungen der Fibonacci-Zahlen sehen wie folgt aus:

1. Start: F(0) = 0, F(1) = 1
2. Nächste Zahl: F(2) = F(1) + F(0) = 1 + 0 = 1
3. Nächste Zahl: F(3) = F(2) + F(1) = 1 + 1 = 2
4. Nächste Zahl: F(4) = F(3) + F(2) = 2 + 1 = 3
5. Nächste Zahl: F(5) = F(4) + F(3) = 3 + 2 = 5
6. Nächste Zahl: F(6) = F(5) + F(4) = 5 + 3 = 8
7. Nächste Zahl: F(7) = F(6) + F(5) = 8 + 5 = 13

Die ersten Zahlen der Fibonacci-Reihe sind also:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Formel:

• F(0) = 0
• F(1) = 1
• Für n ≥ 2: F(n) = F(n-1) + F(n-2)

Anwendungen der Fibonacci-Zahlen:

• Mathematik: Fibonacci-Zahlen tauchen in der Zahlentheorie und Kombinatorik auf. Sie haben Verbindungen zu Teilbarkeitsregeln, goldenem Schnitt und Pascalschem Dreieck.

• Informatik: Fibonacci-Zahlen werden in Algorithmen und Datenstrukturen verwendet, wie etwa in der Fibonacci-Suche und Fibonacci-Heaps. Sie sind auch in der Dynamischen Programmierung von Bedeutung.

• Biologie: In der Natur sind Fibonacci-Zahlen bei der Anordnung von Blättern, Blütenblättern, Fruchtständen (wie Tannenzapfen oder Sonnenblumen) sowie bei der Wachstumsstruktur von Populationen zu finden. Diese natürliche Optimierung wird oft als Fibonacci-Phyllotaxis bezeichnet.

• Kunst und Architektur: Der Goldene Schnitt – ein Verhältnis, das eng mit der Fibonacci-Reihe verbunden ist – wird in Kunstwerken und architektonischen Entwürfen verwendet, um ästhetische Proportionen zu erreichen. Bekannte Beispiele sind das Parthenon in Griechenland oder Gemälde der Renaissance.

Rekursiv vs. iterativ

📘 Unterschied zwischen rekursiv und iterativ:

• Rekursiv: Bei einem rekursiven Algorithmus ruft sich die Funktion selbst auf, bis eine Basisbedingung erreicht ist. Rekursion ist oft eleganter und direkter, spiegelt aber nicht immer die effizienteste Lösung wider, da sie viele wiederholte Berechnungen machen kann und zusätzlichen Speicher für den Rekursionsstapel benötigt.

• Iterativ: Ein iterativer Algorithmus verwendet Schleifen (wie for oder while), um wiederholte Berechnungen durchzuführen. Iteration ist in der Regel effizienter, da sie weniger Speicher benötigt und keine wiederholten Berechnungen macht, was sie insbesondere bei großen Problemen (wie Fibonacci) schneller und ressourcenschonender macht.

1. Ein iterativer Algorithmus

Der iterative Algorithmus zur Berechnung der n-ten Fibonacci-Zahl verwendet eine Schleife, um die Werte der Fibonacci-Zahlen zu berechnen, anstatt rekursive Funktionsaufrufe zu verwenden.

Code:

def fibi (n):
    a = 0
    b = 1
    for i in range(n):
        hilf = a + b
        a = b
        b = hilf
    return a
 
print(fibi(40))

Erklärung:

• Initialisierung:

  • Der Algorithmus beginnt mit zwei Variablen a und b, die die ersten beiden Fibonacci-Zahlen speichern.
    • a = 0 ist die 0-te Fibonacci-Zahl.
    • b = 1 ist die 1-te Fibonacci-Zahl.

• Schleife:

  • Die for-Schleife läuft n Mal (von i = 0 bis i = n-1), um die n-te Fibonacci-Zahl zu berechnen.

  • In jedem Schleifendurchlauf wird die Variable hilf als Summe der aktuellen Werte von a und b berechnet:

    hilf = a + b

    Dies ist die nächste Fibonacci-Zahl, die auf der Addition der beiden vorherigen Fibonacci-Zahlen basiert.

  • Danach wird a auf den Wert von b gesetzt, und b wird auf den neuen Fibonacci-Wert (in hilf) gesetzt:

    a = b
    b = hilf

    Auf diese Weise werden die beiden letzten Fibonacci-Zahlen für den nächsten Schleifendurchlauf aktualisiert.

• Rückgabewert:

  • Nach dem Ende der Schleife enthält die Variable a die n-te Fibonacci-Zahl. Diese wird dann zurückgegeben.

Beispiel:

• Wenn du fibi(5) aufrufst:
  • Die Schleife durchläuft 5 Iterationen:
    • a = 0, b = 1 → a = 1, b = 1 → a = 1, b = 2 → a = 2, b = 3 → a = 3, b = 5.
  • Nach der 5. Iteration ist a = 5, was die 5-te Fibonacci-Zahl ist.

Zeit- und Speicherkomplexität:

• Zeitkomplexität: O(n) – Der Algorithmus durchläuft n Iterationen, was bedeutet, dass die Anzahl der Rechenschritte linear zur Eingabegröße n ist.
• Speicherkomplexität: O(1) – Es werden nur eine konstante Anzahl von Variablen (a, b und hilf) verwendet, unabhängig von der Eingabegröße n.

Vorteile:

• Der iterative Ansatz ist sehr effizient, insbesondere im Vergleich zu rekursiven Ansätzen, da er keine unnötigen Berechnungen durchführt und auch keine Speicherprobleme durch zu viele Rekursionsaufrufe entstehen.

---

2. Ein rekursiver Algorithmus zur Berechnung der n-ten Fibonacci-Zahl

Rekursiver Algorithmus

Der rekursive Ansatz zur Berechnung der n-ten Fibonacci-Zahl folgt der mathematischen Definition der Fibonacci-Folge:

• Fibonacci-Folge:
  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) für n ≥ 2

Die Idee ist, die Fibonacci-Zahl als Summe der zwei vorhergehenden Fibonacci-Zahlen zu berechnen. Der Algorithmus ruft sich selbst rekursiv auf, bis die Basisfälle F(0) und F(1) erreicht werden.

Python-Code:

def fibi2(n):
    if n <= 1:
        return n
    else:
        return fibi2(n-1) + fibi2(n-2)
 
print("Rekursiv: " + str(fibi2(40)))  # Ausgabe: 102334155

Erklärung:

• Basisfälle: Wenn n <= 1, wird n direkt zurückgegeben, da die ersten beiden Fibonacci-Zahlen bekannt sind: F(0) = 0 und F(1) = 1.
• Rekursiver Aufruf: Für n > 1 wird die Funktion rekursiv mit den beiden Werten n-1 und n-2 aufgerufen. Die Rückgabewerte dieser beiden Funktionsaufrufe werden addiert, um die Fibonacci-Zahl für n zu berechnen.
• Zeitkomplexität: Der rekursive Algorithmus hat eine Zeitkomplexität von O(2^n), da jeder Aufruf zwei weitere rekursive Aufrufe erzeugt. Dies macht den Algorithmus für große Werte von n ineffizient.
• Speicherkomplexität: Die Speicherkomplexität beträgt O(n), da der Rekursionsstapel maximal n tief ist.

Beispiel:

• Eingabe: fibi2(5)
  • Aufrufe: fibi2(5) -> fibi2(4) + fibi2(3) -> fibi2(3) + fibi2(2) + fibi2(2) + fibi2(1) -> …
  • Ergebnis: 5
• Eingabe: fibi2(40)
  • Ergebnis: 102334155

Vorteile und Nachteile:

• Vorteile: Der rekursive Ansatz ist elegant und einfach zu verstehen, da er direkt der mathematischen Definition der Fibonacci-Zahlen folgt.
• Nachteile: Aufgrund der vielen rekursiven Aufrufe und der Tatsache, dass viele Berechnungen mehrfach durchgeführt werden, ist dieser Ansatz sehr ineffizient für größere n. Eine Optimierung, z.B. durch Memoization, könnte diesen Nachteil beheben.

---

3. Welcher Ansatz ist vorzuziehen, welcher ist eleganter?

• Rekursiver Ansatz: Eleganter, da er die mathematische Definition direkt widerspiegelt. Allerdings ist er ineffizient, da viele Berechnungen wiederholt werden und die Laufzeit exponentiell ansteigt.

• Iterativer Ansatz: Deutlich effizienter mit einer linearen Laufzeit (O(n)) und konstantem Speicherbedarf (O(1)). Er vermeidet unnötige Wiederholungen und ist besser für große n geeignet.

Fazit:

• Der rekursive Ansatz ist eleganter.
• Der iterative Ansatz ist in der Praxis effizienter und vorzuziehen.
• → In der Praxis wird der iterative Ansatz bevorzugt, da er effizienter ist, auch wenn der rekursive Ansatz die mathematische Definition direkter widerspiegelt

4. Schreiben Sie ohne Verwendung einer Schleife:

a) Eine rekursive Funktion, die die Zeichen einer Zeichenkette nacheinander ausgibt:

Pseudocode:

1. Wenn die Zeichenkette nicht leer ist:
   • Gib das erste Zeichen aus.
   • Entferne das erste Zeichen aus der Zeichenkette.
   • Rufe die Funktion mit der verkürzten Zeichenkette erneut auf.
2. Wiederhole dies, bis die Zeichenkette leer ist.

def rekursive_ausgabe_vorwaerts(kette):
    if kette:
        print(kette[0], end="")
        kette = kette[1:]
        rekursive_ausgabe_vorwaerts(kette)
 
# Beispielaufruf
zeichenkette = "Hallo"
rekursive_ausgabe_vorwaerts(zeichenkette)
print()

Erklärung:

• Die Funktion beginnt mit der vollen Zeichenkette und druckt immer das erste Zeichen. Anschließend wird der Rest der Zeichenkette ohne das erste Zeichen als neue Eingabe verwendet, und die Funktion ruft sich selbst auf. Dies wird so lange wiederholt, bis die Zeichenkette leer ist. Auf diese Weise werden die Zeichen nacheinander in ihrer ursprünglichen Reihenfolge ausgegeben.

b) Eine rekursive Funktion, die die Zeichen der Zeichenkette in umgekehrter Reihenfolge druckt:

def rekursive_ausgabe_rueckwaerts(kette):
    if kette:  # Prüft, ob die Zeichenkette nicht leer ist
        rekursive_ausgabe_rueckwaerts(kette[1:])  # Rekursiver Aufruf mit dem Rest der Zeichenkette (ohne das erste Zeichen)
        print(kette[0], end="")  # Gibt das erste Zeichen der aktuellen Zeichenkette aus
 
# Beispielaufruf
zeichenkette = "Hallo"
rekursive_ausgabe_rueckwaerts(zeichenkette)
print()  # Fügt nach der Ausgabe eine neue Zeile hinzu

Schritt-für-Schritt-Erklärung:

• if kette:

  • Prüft, ob die Zeichenkette nicht leer ist (Basisfall der Rekursion).
  • Falls leer, wird die Rekursion beendet.

• rekursive_ausgabe_rueckwaerts(kette[1:])

  • Führt die Funktion rekursiv mit der Zeichenkette ohne das erste Zeichen aus.
  • Dies verkürzt die Zeichenkette bei jedem Rekursionsschritt, bis sie leer ist.

• print(kette[0], end="")

  • Nachdem die Rekursion den letzten Aufruf erreicht hat (leere Zeichenkette), werden die Zeichen auf dem Rückweg ausgegeben.
  • Druckt das aktuelle Zeichen (kette[0]) aus, sodass die Zeichen in umgekehrter Reihenfolge erscheinen.

• print()

  • Fügt eine neue Zeile nach der Ausgabe der Zeichen hinzu, um den Cursor in die nächste Zeile zu setzen.

Beispiel mit "Hallo":

1. "Hallo" → rekursiver Aufruf mit "allo"
2. "allo" → rekursiver Aufruf mit "llo"
3. "llo" → rekursiver Aufruf mit "lo"
4. "lo" → rekursiver Aufruf mit "o"
5. "o" → rekursiver Aufruf mit "" (leere Zeichenkette, Ende der Rekursion)
6. Auf dem Rückweg wird ausgegeben: "o", "l", "l", "a", "H"

Wichtige Punkte:

• Die Rekursion läuft bis zum Ende der Zeichenkette, bevor die Ausgabe startet.
• Durch das Drucken der Zeichen beim Rückweg erscheinen sie in umgekehrter Reihenfolge.
• Basisfall: Die Rekursion stoppt, wenn die Zeichenkette leer ist.

Zusammenfassung der Idee:

• Vorwärtsausgabe: Die Funktion druckt das erste Zeichen und ruft sich mit dem Rest der Zeichenkette erneut auf. Dadurch werden die Zeichen in ihrer ursprünglichen Reihenfolge gedruckt.
• Rückwärtsausgabe: Die Funktion ruft sich zuerst rekursiv mit dem Rest der Zeichenkette auf und druckt das Zeichen erst danach. Dies führt dazu, dass die Zeichen in umgekehrter Reihenfolge erscheinen.

Beide Funktionen verwenden Rekursion, um jedes Zeichen der Zeichenkette ohne Schleifen zu bearbeiten und auszugeben.

---

5. Diskutieren Sie, wann rekursive Algorithmen besser sind als iterative und wann nicht.

Kurzzusammenfassung

Rekursive und iterative Algorithmen sind zwei Ansätze zur Problemlösung.

Rekursive Algorithmen:

• Vorteile: Einfach zu schreiben und zu verstehen, gut für selbstähnliche Probleme (z. B. Fibonacci).
• Nachteile: Hoher Speicherverbrauch und langsamer bei tiefen Rekursionen (Risiko von Stack Overflow).

Iterative Algorithmen:

• Vorteile: Effizienter, benötigen weniger Speicher und sind für große Probleme geeignet.
• Nachteile: Komplexer und weniger intuitiv, besonders bei natürlichen rekursiven Lösungen.

Fazit:

Rekursion eignet sich für teilbare Probleme, während Iteration besser für Effizienz und Speicherverbrauch ist. Die Wahl hängt von der Situation ab.

Rekursive und iterative Algorithmen sind zwei Ansätze, um Probleme zu lösen. Beide haben Vor- und Nachteile, die man je nach Situation abwägen muss.

Rekursive Algorithmen:

Vorteile:

• Einfachheit: Rekursive Algorithmen sind oft einfacher zu schreiben und zu verstehen, besonders bei Problemen, die sich in kleinere Teilprobleme aufteilen lassen. Ein Beispiel ist die Traversierung eines Baumes: Man kann leicht sagen, „gehe zu jedem Knoten und rufe die Funktion für die Kinderknoten auf“.
• Klarheit bei bestimmten Problemen: Bei Problemen wie der Fibonacci-Reihe oder dem Suchen in Bäumen ist der rekursive Ansatz natürlich und gut lesbar.

Nachteile:

• Hoher Speicherverbrauch: Jeder rekursive Funktionsaufruf wird im sogenannten „Call Stack“ gespeichert. Wenn es viele Aufrufe gibt, kann der Speicher knapp werden, was zu einem Stack Overflow führen kann. Zum Beispiel kann eine naive rekursive Berechnung der Fibonacci-Zahlen für große Werte sehr ineffizient sein.
• Langsam bei großen Problemen: Rekursive Algorithmen können durch die vielen Funktionsaufrufe langsamer sein. Wenn es viele Rekursionsebenen gibt, wie bei tiefen Problemen oder langen Zahlenreihen, wäre eine Schleife oft schneller.

Iterative Algorithmen:

Vorteile:

• Effizienz: Iterative Algorithmen (Schleifen) verbrauchen in der Regel weniger Speicher, da sie keine zusätzlichen Funktionsaufrufe benötigen. Beispielsweise kann man die Fibonacci-Zahlen auch mit einer Schleife berechnen, was viel schneller und speichereffizienter ist.
• Kein Risiko für Stack Overflow: Da Iterationen den Stack nicht füllen, eignen sie sich gut für sehr große Probleme, bei denen eine Rekursion abstürzen könnte.

Nachteile:

• Komplexität des Codes: Iterative Algorithmen können manchmal komplizierter und schwerer zu verstehen sein, besonders bei Problemen, die sich natürlich rekursiv lösen lassen. Zum Beispiel erfordert es mehr Aufwand, die Tiefensuche in einem Baum iterativ zu implementieren.

Beispiel:

Nehmen wir das Problem, die Fakultät einer Zahl zu berechnen, z. B. 5! = 5 × 4 × 3 × 2 × 1.

• Rekursiv: Die Fakultät von 5 ist 5 × Fakultät von 4. Das führt zu einem kurzen und klaren Code.
• Iterativ: Man könnte auch eine Schleife verwenden, um alle Zahlen von 5 bis 1 zu multiplizieren. Dies verbraucht weniger Speicher, ist aber weniger intuitiv.

Fazit:

Rekursive Algorithmen sind nützlich, wenn das Problem sich gut in kleinere Teile zerlegen lässt und der Speicherverbrauch nicht zu hoch ist. Iterative Algorithmen sind besser, wenn Effizienz und Speicher wichtig sind, wie bei sehr großen Problemen. Man sollte also je nach Situation entscheiden, welcher Ansatz besser passt.