Python-Algorithmen

Fibonacci mit Rekursion und Memoisierung in Python

In dieser Lektion berechnest du Fibonacci-Zahlen rekursiv und vermeidest mit Memoisierung, bereits bekannte Ergebnisse neu zu berechnen.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Die rekursive Fibonacci-Definition ist schön, aber extrem langsam: Für das 40. Glied werden dieselben kleineren Rechnungen hunderte Millionen Mal wiederholt. Memoization (das Zwischenspeichern von Ergebnissen) behebt das mit einer einzigen Zeile und zeigt eine Kernidee der dynamischen Programmierung.

Stell es dir so vor

Memoization ist wie eine Schülerin, die jede Antwort in ein Heft schreibt. Wird sie wieder nach fib(5) gefragt, rechnet sie nicht neu, sondern liest die Antwort im Heft nach. Jede Frage wird nur einmal gelöst.

Vom Heft zum Code
@cache📓 Ein Heft mit Antworten führen
fibonacci(number - 1) + fibonacci(number - 2)🧮 Mit zwei kleineren Fragen lösen
if number < 2: return number🛑 Die ersten beiden Antworten sind bekannt
fibonacci(10)⚡ Jede kleinere Antwort wird einmal berechnet: schnell
Jedes Ergebnis beim ersten Mal speichern, danach wiederverwenden.
In einem Satz

Memoization speichert das Ergebnis jedes Funktionsaufrufs, abgelegt unter seinen Argumenten. Wiederholte Aufrufe geben dann das gespeicherte Ergebnis zurück, statt neu zu rechnen.

Das Wichtigste

  1. if number < 2: return number liefert die ersten beiden Glieder, 0 und 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) folgt direkt der Definition.
  3. @cache aus functools merkt sich jedes Ergebnis, sodass jedes fibonacci(k) nur einmal läuft.
  4. Ohne @cache würde fibonacci(10) 177 Aufrufe machen, mit Cache nur 11.

Wann verwendet man das?

  • Rekursive Funktionen, die dieselben Teilprobleme wiederholen: Wege in einem Gitter, Münzwechsel, Wortzerlegung.
  • Die Idee hinter dynamischer Programmierung lernen.
  • Jede reine Funktion beschleunigen, die oft mit denselben Argumenten aufgerufen wird.

Wann du es nicht brauchst

  • Funktionen mit Seiteneffekten oder Ergebnissen, die sich mit der Zeit ändern: Der Cache würde veraltete Antworten liefern.
  • Sehr tiefe Rekursion: Selbst mit Cache kann fib(5000) das Rekursionslimit überschreiten. Eine Schleife vermeidet das.

So funktioniert es

Klicke auf Schritt, um jedem Aufruf zu folgen. Achte darauf, wie fib dieselben kleineren Werte immer wieder berechnet - deshalb ist die einfache Version langsam.

Beispielcode

Code ausführen →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

55

Erklärung des Codes

Der Decorator @cache merkt sich automatisch das Ergebnis der Funktion für jeden Eingabewert. Ist fibonacci(8) einmal berechnet, holen sich spätere Aufrufe nur noch das fertige Ergebnis. So sinkt die Laufzeit von exponentiell auf O(n), dafür braucht man O(n) Speicher für die gespeicherten Ergebnisse.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Rekursion ohne Cache

Dieselben Werte werden immer wieder neu berechnet, und fib(40) dauert viele Sekunden.

Problem
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)
Lösung
@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges