Rekursion, fürsorgliche Browser, vorherbestimmte Zufallszahlen
oder
Wie man den Stack verschont

Der Begriff Rekursion kommt aus dem Lateinischen und bedeutet soviel wie Zurücklaufen oder -eilen. Man sollte meinen, ein solch bildhafter Ausdruck lasse nicht viel Interpretationsspielraum, aber verschiedene Fachrichtungen beschäftigen sich mit ganz unterschiedlichen Aspekten.

Die ehrwürdigen mathematischen Wissenschaften genießen bei vielen Programmierern kein hohes Ansehen; da aber die Erstellung brauchbarer Algorithmen ohne mathematische Kenntnisse kaum möglich ist, werden Sie den folgenden Exkurs über sich ergehen lassen müssen. Ich verspreche, es einfach zu halten und mich kurz zu fassen.

Wenn Mathematiker den Begriff Rekursion hören, denken sie meist1 an rekursive Mengen. Eine rekursive Menge ist eine Untermenge einer größeren Menge, deren Elemente sich zweifelsfrei dieser Untermenge zuordnen lassen, wenn sie eine bestimmte Eigenschaft besitzen (oder eben nicht). Ein klassisches Beispiel sind die geraden Zahlen innerhalb der natürlichen Zahlen2; es sollte bei jeder natürlichen Zahl problemlos zu unterscheiden sein, ob sie gerade oder nicht-gerade ist. Beispiele rekursiver Mengen finden sich auch im wirklichen Leben, etwa die der Nadelbäume innerhalb der Menge der Bäume oder die der Fußballbegeisterten3 unter den Menschen. Das erste Beispiel ist für das Verständnis rekursiver Mengen besonders praktisch, da das intuitive Gegenstück zu den geraden Zahlen - die ungeraden Zahlen - ebenfalls eine rekursive Menge bilden; zwischen den beiden gibt es keine Überschneidungen, und zusammengenommen lassen sie keine natürlichen Zahlen übrig. Das ist nicht immer der Fall - teilt man die Tiere in Vögel und Fische ein, kann man problemlos zwischen Vögeln und Nicht-Vögeln unterscheiden, genauso zwischen Fischen und Nicht-Fischen4; Katzen und Ameisen allerdings müssen sowohl den Nicht-Vögeln als auch den Nicht-Fischen zugeordnet werden. Selbst die Einteilung in Säugetiere und solche, die Eier legen, wird durch die Existenz des Schnabeltiers erschwert.

Ungeachtet mancher Schwierigkeiten in der zoologischen Taxonomie klang es bis jetzt ziemlich einfach - und das ist es auch. Die Erwähnung rekursiver Mengen hat natürlich nur Sinn, wenn es auch nichtrekursive Mengen gibt. Eine solche zu konstruieren ist nicht schwer, als Beispiel mögen die Glückszahlen des äußerst verschwiegenen tibetanischen Mönchs Tsao-Wun5 dienen. Die Menge der Glückszahlen Tsao-Wuns ist wohldefiniert; selbst wenn er gar keine Glückszahlen hat, ist das aus mathematischer Sicht unproblematisch, in diesem Fall wäre die gesuchte Menge eben die leere Menge. Ein Problem für die Bildung einer rekursiven Menge ist aber Tsao-Wuns Verschwiegenheit: Wenn er niemandem über seine Glückszahlen berichtet hat, gibt es auch keine Möglichkeit, einer Zahl die Eigenschaft, eine Glückszahl zu sein, zu- oder abzusprechen.

War das Verständnis rekursiver Mengen noch leicht, erscheinen die nichtrekursiven Mengen geradezu als trivial, und man fragt sich instinktiv, zu welchem Zweck über derartige Fragen überhaupt nachgedacht wird. Die Feinheit kommt jetzt. Stellen Sie sich vor, Sie sollten die Menschen dieses Landes in solche, die mit einem bisherigen oder zukünftigen Bundeskanzler6 verwandt sind einteilen - und in solche, die es nicht sind. Eine sinnvolle Vorgehensweise wäre, von einer Liste der bisherigen Kanzler auszugehen und die Namen ihrer Verwandten herauszufinden; so finden sich Personen, die der Menge angehören müssen7. Allerdings dürfen die anderen angesichts der Forderung, auch Verwandtschaft mit einem zukünftigen Bundeskanzler als Kriterium anzusehen, keinesfalls bedenkenlos der Menge der Nicht-Verwandten zugeschlagen werden; zukünftige Ereignisse könnten diese Entscheidung revidieren. Die Problematik würde auch dann nicht aufgehoben, wenn man bei einigen (aber eben nicht allen), bei denen keine Verwandtschaft festgestellt werden konnte, sicher sein könnte, daß nie eine bestehen wird. Allgemein gesprochen gilt eine Menge als rekursiv aufzählbar, aber nicht rekursiv8, wenn höchstens die Elemente der Menge, nicht jedoch die ihres Komplements (also ihres Gegenstücks) vollständig aufzählbar sind. Anders ausgedrückt: Alle Elemente, denen man attestiert, zur rekursiv aufzählbaren Menge zu gehören, sind dort richtig eingeordnet. Es könnte allerdings auch noch andere Elemente geben, die man der rekursiv aufzählbaren Menge zuschlagen müßte. Die Feststellung, ein Element gehöre nicht zur Menge, ist stets nur auf Verdacht und könnte durch kommende Ereignisse widerrufen werden.

Auch wenn die Unterscheidung zwischen rekursiv und rekursiv aufzählbar im letzten Beispiel allein am Begriff zukünftig hing, ist leicht einzusehen, daß auch ohne dieses Kriterium die Problematik viel schwerwiegender ist als bei der korrekten Einordnung von Walen und Schnabeltieren, da selbst die Feststellung ist nicht mit einem bisherigen Bundeskanzler verwandt immer nur unter Vorbehalt getroffen werden kann - zumindestens solange, bis man alle Kanzler und ihre Verwandten (die ja auch zweiten, dritten oder wer-weiß-wievielten Grades sein könnten) gefunden hat. Dem Ärgernis, dringend benötigte Informationen erst durch künftige Operationen in Erfahrung bringen zu können, begegnet man auch in der Informatik; bezeichnenderweise nennt sich dort der bevorzugte Lösungsansatz rekursive Funktion.


weiter: Programmiertechnische Grundlagen 

1 Diese Sichtweise ist zugegebenermaßen etwas eingeschränkt. Mathematik und vor allen Dingen Logik haben auch andere Eigenschaften der Rekursion untersucht. Wikipedia: Rekursion  ↑ 

2 Natürliche Zahlen sind solche, die sich zum Zählen verwenden lassen (also 1, 2, 3...). Ob 0 zu den natürlichen Zahlen gezählt werden soll, war lange Zeit ungeklärt; nach moderner Auffassung gehört 0 dazu.  ↑ 

3 Die Frage, wie die Grenzlinie zwischen fußballbegeistert und nicht-fußballbegeistert verläuft, bedürfte natürlich einer Klärung. Soll eine Person, die begeistert Länderspiele betrachtet, Ligaspiele aber verschmäht, als fußballbegeistert gelten? Ist es notwendig, sich sowohl für Frauen- als auch für Männerfußball zu begeistern? Gilt die Einteilung ein Leben lang, ist also ein ehemaliger Fußballfan, der das Interesse verloren hat, immer noch als fußballbegeistert anzusehen? Die Mathematik sieht sich als über derartige praktische Probleme erhaben und klassifiziert die Grundfrage als prinzipiell entscheidbar.  ↑ 

4 Ganz problemlos ist bekanntlich auch das nicht. Ich habe nichts dagegen einzuwenden, wenn Wale nicht als Fische gelten, aber die oft geäußerte Begründung Der Wal ist kein Fisch, weil er ein Säugetier ist habe ich nie verstanden.  ↑ 

5 Sie brauchen diesen Namen nicht nachzuschlagen; ich habe ihn gerade frei erfunden.  ↑ 

6 Wie bei solchen Gelegenheiten üblich, sind auch mit dem Begriff Bundeskanzler Menschen beiderlei Geschlechts gemeint. Zudem soll die Problemstellung nur als Beispiel dienen und interessiert mich inhaltlich überhaupt nicht.  ↑ 

7 Bezüglich der Frage, zu welcher Menge die Bundeskanzler selbst gehören, siehe Wikipedia: Barbier-Paradoxon.  ↑ 

8 Alle rekursiven Mengen sind auch gleichzeitig rekursiv aufzählbar; deswegen könnte eine als rekursiv aufzählbar bezeichnete Menge auch rekursiv sein. In der Praxis ist ein solcher Sprachgebrauch allerdings verwirrend. Nach Möglichkeit sollte man nur solche Mengen als rekursiv aufzählbar bezeichnen, bei denen man sich einigermaßen sicher ist, daß sie nicht rekursiv sind.  ↑