Die Bibliothek · Informatik & KITafel № 476 · Folio III
ILL. № 476
CS·KI
Plate — Rekursion
·Tafel № 476

Rekursion

Eine Funktion, die sich selbst aufruft — produktiv, sofern der rekursive Fall die Eingabe verkleinert.
Als Nächstes empfohlen → Datenstrukturen · CS·KI
Facetten
  • A function defined in terms of itselfnoch nicht geprüft
  • Base case, recursive case, and trustnoch nicht geprüft
  • Trees, divide-and-conquer, and parsingnoch nicht geprüft
  • Stack overflow and exponential redundant worknoch nicht geprüft
Der Beitrag

Im Jahr 1936 formalisierten drei Mathematiker — Alonzo Church in Princeton, Alan Turing in Cambridge, Stephen Kleene an Churchs Seite — unabhängig voneinander, was es heißt, zu rechnen. Churchs Lambda-Kalkül, Turings Maschinen, die allgemein rekursiven Funktionen von Gödel, Herbrand und Kleene — drei Formalismen, die sich, einigermaßen verblüffend, als exakt gleichwertig in ihrer Ausdrucksstärke erwiesen. Bekannt wurde das Ergebnis als Church-Turing-These: jede intuitiv berechenbare Funktion lässt sich in jedem dieser Systeme ausdrücken. Von den dreien kommt der Denkweise arbeitender Programmierer die Rekursion am nächsten — der Kniff, eine Funktion über sich selbst zu definieren. Die Fakultät: n! = n × (n-1)!, mit dem Basisfall 0! = 1. Wenn man es zum ersten Mal funktionieren sieht, wirkt es seltsam — die Funktion ruft sich selbst, und das Ergebnis ist trotzdem endlich, korrekt und nützlich.

Die Rekursion greift, sobald sich ein Problem in kleinere Instanzen desselben Problems zerlegen lässt. Das Rezept ist stets dasselbe: (1) Basisfall — die kleinste Instanz, deren Antwort unmittelbar feststeht; (2) Rekursionsfall — drücke die Antwort der aktuellen Instanz durch die einer streng kleineren aus; (3) vertraue der Rekursion — nimm an, die Funktion arbeite auf kleineren Eingaben, und rufe sie auf. Mathematisch dahinter steht die Induktion: eine rekursive Definition ist korrekt, sobald der Basisfall stimmt und der Rekursionsfall die Antwort der kleineren Eingabe richtig zusammensetzt. Wo Rekursion glänzt: beim Durchlaufen von Bäumen und Graphen, in Teile-und-herrsche-Algorithmen (Mergesort, Quicksort, FFT), beim Parsen — Recursive-Descent-Parser fallen unmittelbar aus rekursiven Grammatiken —, in funktionalen Programmieridiomen (map, filter, fold) und im Sprachentwurf selbst (Lisp, die zweitälteste Programmiersprache, behandelt Programme und Daten als rekursiv strukturierte Listen). Wo Rekursion versagt oder Sorgfalt verlangt: tiefe Rekursion sprengt den Aufrufstapel — die meisten Sprachen begrenzen die Stapeltiefe auf wenige Tausend Rahmen, sehr tiefe Rekursionen brauchen Tail-Call-Optimierung oder ausdrückliche Iteration; naive Rekursion kann exponentiell redundant arbeiten — Fibonacci naiv berechnet macht O(2^n) Aufrufe, weil F(n-1) und F(n-2) ihre Teilbäume immer wieder neu berechnen, und erst Memoisierung oder dynamische Programmierung drückt das auf O(n). Die tiefere Bedeutung der Rekursion: sie ist die schlichteste konkrete Demonstration, dass Selbstbezug im Rechnen nicht paradox, sondern konstruktiv ist. Derselbe Kniff, unbedacht angewandt, erzeugt Russells Paradox und Gödels Unvollständigkeitssatz; sorgfältig angewandt, brauchbare Programme. Die Trennlinie zwischen produktivem und paradoxem Selbstbezug verläuft grob daran, ob der Rekursionsfall das Problem strikt verkleinert.

Warum jetztRekursion ist ein fundamentales Primitiv heutiger Informatik, im Produktionscode aber nicht immer das richtige Idiom. Iteration ist oft klarer und schneller; moderne Compiler übersetzen endrekursiven Code meist in Iteration, bei nicht-endrekursiven Aufrufen helfen sie nicht. Funktionale Programmiersprachen (Haskell, Lisp, Scheme, Clojure, Erlang, Elixir) setzen die Rekursion als primäres Steuerprimitiv. Baumstrukturierte Daten — DOM-Bäume, Dateisysteme, ASTs, JSON, Entscheidungsbäume, Szenegraphen im 3D-Rendering — sind in moderner Software allgegenwärtig, und Rekursion ist der natürliche Weg, sie zu durchlaufen. Noam Chomskys generative Grammatik von 1957, die Gründungsthese der modernen Linguistik, lautet, dass die menschliche Sprache rekursiv ist — Sätze enthalten Sätze, und diese rekursive Struktur erlaubt es einer endlichen Grammatik, eine unendliche Ausdrucksspanne zu tragen. In LLMs nutzen Transformer-Modelle Rekursion architektonisch nicht im strengen Sinn; ob ein System ohne ausdrückliches Rekursionsprimitiv rekursiv schließen kann, gehört zu den offenen empirischen Fragen heutiger KI-Forschung.