Rekursion (v. lat. recurrere "zurücklaufen"), Selbstbezug. Rekursion tritt auf, wenn ein Objekt direkt oder indirekt►auf sich selbst verweist.

Ein Beispiel für Rekursion ist der Satz "Dieser Satz ist wahr". Rekursion kann zu merkwürdigen Widersprüchen führen, wie man feststellt, wenn man darüber nachgrübelt, ob der Satz "Dieser Satz ist unwahr" unwahr ist. Indirekte Rekursion ist ein gegenseitiger Bezug mehrerer Objekte, wie in "Der folgende Satz ist wahr", "Der vorhergehende Satz ist unwahr". Rekursive Sätze lassen zuweilen einen Hauch von Unendlichkeit spüren: "'Wird mit jeder Wiederholung länger' wird mit jeder Wiederholung länger." Oder sie können den Leser schlicht überfordern, etwa mit "Lesen Sie diesen Satz nicht!".

Nicht nur Sätze können rekursiv sein. Eine unendliche graphische Rekursion ist auch als Droste-Effekt bekannt, zu Ehren der holländischen Schokoladenmarke Droste. Ihre Kakaopackungen tragen das Bild einer Krankenschwester, die eine Kakaopackung mit dem Bild einer Krankenschwester trägt, die eine Kakaopackung mit dem Bild einer Krankenschwester trägt.


Der Droste-Effekt*

Dieses Verpackungsdesign wurde seit 100 Jahren nicht geändert. Somit repräsentiert es in der schnelllebigen Welt der Werbegrafik selbst das beinahe ►Ewige. Doch stößt der Droste-Effekt wegen der notwendigen Verkleinerungen rasch an die Grenzen des drucktechnisch Machbaren. Kann man den gleichen Effekt in einem Bild auch ohne Verkleinerungen und mit echter Unendlichkeit erreichen? Man ist geneigt, dies für unmöglich zu halten. Doch ►M.C. Escher schaffte es durch eine Verzerrung des Raums zu einer endlosen Spirale:

Escher, Bildergalerie, 1956**

Manche Internetprojekte spielen mit unendlichem Selbstbezug. Das ►Infinite Cat Project begann mit dem Bild einer Katze, die einen Computermonitor betrachtet. Daraufhin postete ein Besucher das Bild seiner Katze, die einen Computermonitor betrachtet, auf dem eine Katze einen Computermonitor betrachtet. Die Idee wurde fortgesetzt. Jeder Besucher ist aufgefordert, mittels eines Monitors und einer Katze ein Stück zu dieser potentiellen Unendlichkeit beizutragen, die mittlerweile (2008) bei der 1075. Katze angelangt ist.

In der Programmierung bedeutet Rekursion eine ►Funktion, die zur Berechnung eines Zwischen- oder Endergebnisses wiederholt sich selbst ausführt. Eine solche Computerfunktion muss die Ausführungen ihrer selbst durch eine Abbruchbedingung begrenzen. Andernfalls entsteht eine unendliche Rekursion, ein Sonderfall der von Programmierern gefürchteten ►Endlosschleife. Hierbei wiederholen sich die Selbstausführungen der Funktion unendlich oft, was in der Praxis zum Absturz des Computers führt.

Es ist gar nicht so einfach, festzustellen, ob eine Abbruchbedingung eine rekursive Funktion bei allen möglichen Eingabedaten immer zuverlässig abbricht. In der Tat bewies der britische Mathematiker Alan Turing schon 1936, dass die Korrektheit von Abbruchbedingungen im Allgemeinen nicht beweisen werden kann (Halteproblem). Den Beweis finden Sie unter ►Endlosschleife.


* Mit freundlicher Genehmigung der Droste B.V.

** Die Rechte an allen Escher-Grafiken liegen bei der M.C. Escher Company B.V., http://www.mcescher.com

© Johann Christian Lotter   ■  Infinity  ■  Links  ■  Forum