Fibonacci mit Rekursion und Memoization
Memoization speichert bereits berechnete Funktionswerte in einem Cache.
Was ist Fibonacci mit Rekursion und Memoization?
Memoization speichert bereits berechnete Funktionswerte in einem Cache.
Berechne Fibonacci-Zahlen rekursiv, ohne Ergebnisse mehrfach zu berechnen.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Beispielcode
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))Erwartete Ausgabe
55So funktioniert es
Der Cache reduziert die exponentielle naive Rekursion auf O(n) Zeit, benötigt jedoch O(n) zusätzlichen Speicher.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.