====== LU03b - Rekursion ====== Die Rekursion ist eine Technik in der Programmierung, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen. Rekursive Funktionen bestehen normalerweise aus zwei Teilen: dem Basisfall, der das Ende der Rekursion markiert, und dem rekursiven Fall, der die Funktion erneut mit einem Teilproblem aufruft. Rekursion kann für viele Probleme eine elegante und effektive Lösung bieten. Rekursion muss mit Sorgfalt verwendet werden, da sie ohne einen klaren Basisfall zu einer Endlosschleife führen kann. ===== Animation: Call Stack und Aufrufbaum ===== Rekursion ist schwer zu lesen, weil mehrere Aufrufe derselben Funktion gleichzeitig offen sind. Die Animation macht das sichtbar: * **Tab 1** zeigt am Beispiel ''factorial(3)'', wie sich vier Frames stapeln, bis der Basisfall erreicht ist – und wie die eigentliche Rechnung erst auf dem Rückweg passiert. * **Tab 2** zeigt am Beispiel ''fibonacci(4)'', dass hier kein Stapel, sondern ein **Baum** entsteht – und dass dabei dieselben Teilprobleme mehrfach berechnet werden. {{url>https://templates-python.github.io/m323_html/lu03/rekursion.html 100%,860px noborder|Animation: Rekursion – Call Stack und Aufrufbaum}} Die Animation verwendet kleinere Zahlen als die Beispiele unten (''factorial(3)'' statt ''factorial(5)'', ''fibonacci(4)'' statt ''fibonacci(6)''), damit Stack und Baum vollständig auf den Bildschirm passen. Das Prinzip ist identisch. ===== Beispiel 1: Fakultät ===== Die Fakultät einer Zahl ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Sie wird oft mit dem Symbol ''!'' dargestellt, z.B. ''5!=5×4×3×2×1=120''. def factorial(n): if n == 0: # Basisfall return 1 else: # Rekursiver Fall return n * factorial(n-1) if __name__ == '__main__': print(factorial(5)) # Ausgabe: 120 ===== Beispiel 2: Fibonacci-Reihe ===== Die Fibonacci-Reihe ist eine Folge von Zahlen, bei der jede Zahl die Summe der beiden vorhergehenden ist. Die ersten zwei Zahlen in der Fibonacci-Reihe sind 0 und 1. def fibonacci(n): if n == 0: # Basisfall 1 return 0 elif n == 1: # Basisfall 2 return 1 else: # Rekursiver Fall return fibonacci(n-1) + fibonacci(n-2) if __name__ == '__main__': print(fibonacci(6)) # Ausgabe: 8 **Vorsicht bei der Zählung:** Die Folge startet bei ''n = 0'', nicht bei ''n = 1''. ^ n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ^ fibonacci | 0 | 1 | 1 | 2 | 3 | 5 | 8 | ''fibonacci(6)'' ist also **8** – die 5 gehört zu ''fibonacci(5)''. Solche Verwechslungen sind bei Reihen, die bei 0 beginnen, die häufigste Fehlerquelle. **Rekursion hat ihren Preis:** Der Aufrufbaum von ''fibonacci(4)'' enthält bereits 9 Aufrufe, obwohl es nur 5 verschiedene Teilprobleme gibt – ''fibonacci(1)'' wird dreimal komplett neu berechnet. Bei ''fibonacci(30)'' sind es über 2,7 Millionen Aufrufe. Wer das vermeiden will, speichert Zwischenergebnisse (Memoization). Tab 2 der Animation oben zeigt die Mehrfachberechnungen farblich markiert. ===== Rekursion in der Praxis ===== Fakultät und Fibonacci sind gute Lernbeispiele, aber ehrliche Praxis sind sie nicht: Beide löst man in echtem Code meist mit einer Schleife. Die berechtigte Frage lautet also: **Wozu braucht man Rekursion überhaupt?** **Die Faustregel:** Rekursion lohnt sich dort, wo die **Datenstruktur oder das Problem selbst verschachtelt** ist – wo also ein Ding wieder Dinge derselben Art enthält. Dann bildet der Code einfach die Form der Daten ab. Ist die Struktur dagegen flach (eine Liste, ein Zähler), ist eine Schleife klarer. ==== Verschachtelte Datenstrukturen ==== * **Dateisystem:** Ein Ordner enthält Dateien //und weitere Ordner//. Jede Suche, jede Grössenberechnung, jedes Backup-Tool und jedes ''os.walk()'' arbeitet rekursiv. * **JSON, XML, HTML:** Ein Objekt enthält Objekte, ein ''
'' enthält weitere ''
''. Jeder Parser und jeder Browser traversiert diese Bäume rekursiv. * **Organigramme und Stücklisten:** „Wer sind alle Mitarbeitenden unter dieser Person?" oder die Stücklistenauflösung im ERP – ein Bauteil besteht aus Bauteilen, die wieder aus Bauteilen bestehen. * **Kommentarbäume:** Antworten auf Antworten auf Kommentare, wie sie jedes Forum darstellt. ==== Divide & Conquer ==== Ein grosses Problem wird in gleichartige kleinere zerlegt: * **Quicksort und Mergesort** – sortiere die zwei Hälften, füge sie zusammen. * **Binäre Suche** – halbiere den Suchbereich, suche weiter in der richtigen Hälfte. * **Kompression** – der Huffman-Baum wird rekursiv aufgebaut und ausgelesen. ==== Suchen und Ausprobieren (Backtracking) ==== * **Sudoku- und Labyrinth-Löser:** Setze einen Wert, versuche rekursiv weiterzukommen, nimm bei einer Sackgasse den Zug zurück. * **Spiele-KI:** Der Minimax-Algorithmus im Schach fragt rekursiv „Was tue ich, wenn der Gegner das tut, worauf ich jenes tue …?" * **Routenplanung:** Die Tiefensuche in einem Graphen ist von Natur aus rekursiv. ==== Weitere Beispiele ==== * **Ray-Tracing:** Trifft ein Lichtstrahl auf einen Spiegel, wird ein neuer Strahl verfolgt – dieselbe Funktion, neuer Startpunkt. * **Fraktale und Terrain-Generierung:** Landschaften in Spielen entstehen, indem eine Fläche immer wieder in kleinere, ähnliche Flächen unterteilt wird. * **Benutzeroberflächen:** Frameworks wie React oder Vue rendern ihren Komponentenbaum rekursiv – eine Komponente enthält Komponenten. **Der Zusammenhang zur funktionalen Programmierung:** In der funktionalen Programmierung ersetzt Rekursion die Schleife vollständig, weil es keine veränderbare Zählvariable geben soll. Rekursion ist dort also nicht nur eine Option für Sonderfälle, sondern das Standardwerkzeug für Wiederholung. Die Aufgabe [[modul:m323:learningunits:lu03:aufgaben:verzeichnisbaum|LU03.A01 - Rekursive Suche in einem Verzeichnisbaum]] greift den ersten Fall direkt auf: eine verschachtelte Struktur, bei der eine Schleife nicht ausreicht. ---- {{tag>M323-LU03 M323-C1B}} [[https://creativecommons.org/licenses/by-nc-sa/4.0/ch/|{{https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png}}]] (c) Kevin Maurizi