Rekursion

Selbstbezug im Programm ist kein Widerspruch, sondern ein Werkzeug: Eine Funktion darf sich selbst aufrufen, solange jeder Aufruf die Eingabe echt verkleinert und ein Basisfall die Kette beendet.

Als Nächstes empfohlen → Peano-Axiome · MATH · T4

Der Beitrag

1936 fielen drei Antworten auf dieselbe Frage zusammen. Alonzo Church in Princeton, Alan Turing in Cambridge und Stephen Kleene an Churchs Seite bestimmten unabhängig voneinander, was Rechnen eigentlich heißt: Church über sein Lambda-Kalkül, Turing über seine Maschinen, Gödel, Herbrand und Kleene über die allgemein rekursiven Funktionen. Dass diese drei Formalismen in ihrer Ausdrucksstärke exakt gleichwertig sind, war die eigentliche Überraschung — bekannt wurde sie als Church-Turing-These: Was immer sich intuitiv berechnen lässt, lässt sich in jedem der drei Systeme ausdrücken. Dem Denken arbeitender Programmierer steht davon die Rekursion am nächsten, der Kniff, eine Funktion durch sich selbst zu erklären. Die Fakultät etwa: n! = n × (n-1)!, dazu der Basisfall 0! = 1. Beim ersten Mal traut man dem Ganzen nicht — die Funktion ruft sich selbst auf, und heraus kommt trotzdem etwas Endliches, Richtiges und Brauchbares.

Rekursion trägt immer dann, wenn sich ein Problem in kleinere Instanzen desselben Problems zerlegen lässt. Das Rezept ändert sich nie: (1) der Basisfall — die kleinste Instanz, deren Antwort man direkt hinschreibt; (2) der Rekursionsfall — die Antwort für die aktuelle Instanz aus der Antwort für eine echt kleinere zusammensetzen; (3) der Rekursion vertrauen — annehmen, die Funktion arbeite auf kleineren Eingaben bereits richtig, und sie aufrufen. Darunter liegt die Induktion: Stimmt der Basisfall und setzt der Rekursionsfall die Antwort der kleineren Eingabe richtig zusammen, dann ist die Definition korrekt. Wo Rekursion glänzt: beim Durchlaufen von Bäumen und Graphen, bei Teile-und-herrsche-Verfahren wie Mergesort, Quicksort und der FFT, beim Parsen, wo Recursive-Descent-Parser unmittelbar aus rekursiven Grammatiken herausfallen, bei funktionalen Idiomen wie map, filter und fold — und im Sprachentwurf selbst: Lisp, die zweitälteste noch gebräuchliche höhere Programmiersprache, behandelt Programme wie Daten als rekursiv strukturierte Listen. Wo Rekursion versagt oder Sorgfalt verlangt: Zu tiefe Rekursion sprengt den Aufrufstapel, denn die meisten Sprachen lassen nur einige Tausend Rahmen zu; wer tiefer muss, braucht Tail-Call-Optimierung oder schlicht Iteration. Und naiv geschrieben kann Rekursion exponentiell doppelte Arbeit leisten: Fibonacci kommt so auf O(2^n) Aufrufe, weil F(n-1) und F(n-2) dieselben Teilbäume immer wieder neu ausrechnen — erst Memoisierung oder dynamische Programmierung drücken das auf O(n). Die tiefere Pointe der Rekursion: Sie ist die schlichteste greifbare Demonstration, dass Selbstbezug im Rechnen nicht paradox, sondern konstruktiv ist. Derselbe Kniff liefert unbedacht angewandt die Russellsche Antinomie der Mengenlehre und Gödels Unvollständigkeitssatz, sorgfältig angewandt dagegen brauchbare Programme. Die Trennlinie zwischen produktivem und paradoxem Selbstbezug verläuft ungefähr dort, ob der Rekursionsfall das Problem echt verkleinert.

Warum jetztIn der heutigen Informatik ist die Rekursion ein grundlegendes Primitiv, im Produktionscode aber nicht immer das passende Idiom. Iteration liest sich oft klarer und läuft schneller; endrekursiven Code übersetzen moderne Compiler meist von selbst in Schleifen, bei nicht endrekursiven Aufrufen sind sie machtlos. Funktionale Programmiersprachen — Haskell, Lisp, Scheme, Clojure, Erlang, Elixir — bauen ihren Kontrollfluss überhaupt erst auf Rekursion auf. Baumförmige Daten wiederum begegnen einem heute überall: DOM-Bäume, Dateisysteme, ASTs, JSON, Entscheidungsbäume, Szenengraphen im 3D-Rendering — und der natürliche Weg, sie abzulaufen, ist rekursiv. Die seit den 1950er Jahren von Noam Chomsky entwickelte generative Grammatik misst rekursiven Strukturen in der menschlichen Sprache große Bedeutung bei: Sätze stecken in Sätzen, und erst diese Schachtelung erklärt, wie eine endliche Grammatik eine unendliche Ausdrucksspanne trägt. In LLMs greifen Transformer-Modelle architektonisch auf nichts dergleichen zurück; ob ein System auch ohne eingebautes Rekursionsprimitiv rekursiv schließen kann, zählt 2026 noch zu den offenen empirischen Fragen der KI-Forschung.