Begriff
Recursion
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Um Rekursion zu verstehen, muss man erst Rekursion verstehen. (Alter Programmierer-Witz). Ernsthaft: Eine Funktion ruft sich selbst auf. Wie russische Matrjoschka-Puppen. Du öffnest eine Puppe, darin ist eine kleinere Puppe (gleiche Funktion öffnen). Das machst du so lange, bis du an der kleinsten Puppe (massiv) ankommst. Das ist der Base Case (Abbruchbedingung). Dann machst du alle Puppen wieder zu.
Merksatz: Eine Programmiertechnik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere Instanzen desselben Problems zerlegt, bis ein Basisfall erreicht ist.
Ordner durchsuchen (das klassische Beispiel):
Ein Ordner enthält Dateien und andere Ordner.
Funktion scanOrdner(path):
- Liste alle Items.
- Wenn Item = Datei -> Drucke Name.
- Wenn Item = Ordner -> Rufe
scanOrdner(Item)auf!
Mit einer for-Schleife ist das extrem schwer (wie tief geschachtelt?). Mit Rekursion sind es 3 Zeilen.
1. Stack Overflow
Jeder Funktionsaufruf belegt ein Stück RAM auf dem Call Stack.
Ruft sich die Funktion 10.000 Mal selbst auf (ohne Base Case), ist der Stack voll.
Crash: StackOverflowError.
Rekursion braucht mehr RAM als Schleifen.
2. Tail Call Optimization (TCO)
In funktionalen Sprachen (Haskell, Elixir) ist Rekursion der einzige Weg (keine Loops).
Damit der Stack nicht platzt, gibt es TCO.
Wenn der rekursive Aufruf das allerletzte ist, was die Funktion tut (return rekursion()),
dann kann der Compiler den aktuellen Stack-Frame überschreiben statt einen neuen draufzulegen.
Es läuft dann intern als Endlosschleife -> Kein Stack Overflow.
Viele Sprachen (Java, Python) können das nicht.
3. Rekursion vs. Iteration
Jedes rekursive Problem kann auch iterativ (mit Stack-Liste und While-Schleife) gelöst werden. Iterativ ist oft schneller und sicherer (kein Stack Limit). Rekursiv ist oft eleganter und lesbarer (bei Bäumen/Graphen).
Trampoline Pattern (TCO in Sprachen ohne TCO)
Sprachen wie JavaScript (V8 Engine NodeJS) oder Python unterstützen nativ keine Tail Call Optimization (TCO). Der Call-Stack wächst unweigerlich an und stirbt oft bei exakt 10.000 Frames. Um dies zu umgehen, nutzt man das Trampoline Pattern. Statt dass sich die rekursive Funktion im Speicher massiv selbst aufruft (tief), gibt sie eine anonyme Funktion (Closure) zurück, die den nächsten rekursiven Schritt repräsentiert. Ein umhüllender Loop (das "Trampolin") führt diese zurückgegebene Funktion immer wieder auf derselben flachen Call-Stack-Ebene aus, bis ein nativer Wert (der Base Case) dropt. So simuliert man endlose Rekursion im RAM (O(1) Space), auch wenn die Sprache keinen Compiler-Support dafür liefert.
Der Y-Combinator
Rekursion braucht zwingend einen Funktions-Namen, um sich selbst referenzieren zu können. Aber was, wenn die Funktion anonym ist (Lambda-Calculus)? Hier kommt die Mindfuck-Klasse der theoretischen Informatik: Der Y-Combinator. Es ist eine Higher-Order Function, die einer anonymen Funktion beibringt, rekursiv zu sein. Stark abstrahiert übergibt der Y-Combinator die Funktion als Argument an sich selbst. Im LISP/Haskell Universum beweist der Y-Combinator mathematisch, dass Variablen-Namen oder Schleifen völlig überflüssig sind, um Turing-Vollständigkeit zu erreichen.
Master Theorem (O-Notation)
Wie misst man den Big-O Zeitaufwand (Performance) eines rekursiven Divide-and-Conquer Algorithmus wie MergeSort?
Rekursion entzieht sich dem simplen Schleifen-Zählen. Hier nutzt die Informatik das Master Theorem.
Es löst Rekurrenzgleichungen der Form T(n) = a*T(n/b) + O(n^d).
Man vergleicht, wie viele Unter-Zweige entstehen (a), wie stark das Problem in der Mitte zerteilt wird (b) und welche Kosten der Overhead des Mergens kostet (n^d). Dieses Formel-Monster liefert als exaktes Resultat, warum Divide & Conquer ($O(N \log N)$) immer Brute-Force Schleifen schlägt.
Quick-Check
Base Case vergessen?
Infinite Loop (endlos). Der Computer friert ein oder crasht sofort. Der häufigste Fehler.Fibonacci?
Das schlechteste Beispiel für Rekursion.fib(n-1) + fib(n-2)ist exponentiell langsam ($O(2^n)$), weil es dieselben Zahlen millionenfach neu berechnet. Man braucht "Memoization" (Caching).Quicksort?
Ein berühmter Sortieralgorithmus (Divide and Conquer), der rein auf Rekursion basiert.