Was versteht man unter Rekursion

Was Rekursion ist, lässt sich am besten mit der alten Geschichte vom Mann mit dem hohlen Zahn erklären. Diese geht so:

Es war einmal ein Mann, der hatte einen hohlen Zahn. In diesem hohlen Zahn befand sich eine Truhe. In der Truhe war ein Brief. In diesem Brief stand: 

In einer etwas vereinfachten und leicht moderneren Form könnte der Sachverhalt so dargestellt werden:

Du kannst ein ähnliches Verhalten beobachten, wenn du dich zwischen zwei parallel aufgestellte Spiegel stellst, dann wird das Spiegelbild vom Spiegel reflektiert, welcher dann wieder das Spiegelbild vom Spiegelbild usw. Da du wahrscheinlich keine zwei parallelen Spiegel zu Verfügung hast, kannst du das gleiche Phänomen auch in einer Videokonferenz erproben. Starte dazu eine Videokonferenz und melde dich dort mit zwei Geräten an. Lasse auf dem Bildschirm des einen Geräts anzeigen, was das andere sieht und richte dann die Kamera des einen Geräts auf den Bildschirm des anderen.

In diesem Fall wird also ein Bild gezeigt, das ein Bild zeigt, welches ein Bild zeigt usw. Grundsätzlich kann man diesen Vorgang in alle Unendlichkeit fortsetzen. Dagegen sprechen aber zwei Dinge. Erstens, selbst wenn du ein Spiegelbild von dir in einem Spiegel anschaust, siehst du nicht gleich unendlich viele Spiegelbilder. Das dauert nämlich ein wenig wegen der Lichtgeschwindigkeit. Ausserdem geht beim Spiegeln immer auch etwas Bildqualität verloren, denn kein Spiegel ist perfekt. Spätestens dann, wenn das Bild kleiner ist als ein einzelnes Atom, wird es wohl mit der Genauigkeit schwierig.

Und wenn wir zweitens daran denken, dass wir einen solchen Sachverhalt auf den Computer übertragen, würde der Computer unendlich lange brauchen, um die Aufgabe zu lösen. Wenn aber der Computer unendlich lange mit dieser Aufgabe beschäftigt ist, wird er nie fertig. Wir sprechen dann von einem Absturz, weil der Computer dieses Programm nie mehr verlassen kann.

Dies alles bedeutet, dass wir in Wirklichkeit zwar Rekursion benutzten können, dort aber immer auch für ein Abbruchkriterium sorgen müssen. Dies bedeutet, dass wir irgendwann aufhören, das Bild im Bild im Bild ... zu zeigen. Wie das genau funktioniert, siehst du gleich am Beispiel eines einfachen Textes und eines Blocks, den du selbst in Snap! schreibst:

Wir speichern also zuerst eine Mitteilung in einer Variablen mit dem Namen "message". Anschliessend übergeben wir diese Mittelung einem selbst geschriebenen Block. Hier siehst du, wie dieser Block aussieht.

Unser Block hat zwei Eingaben - einen Text und eine Zahl - und gibt immer einen Text zurück. Was für einen Text der Block genau zurückgibt, hängt von der übergebenen Zahl ab. Solange diese grösser als Eins ist, besteht der übergebene Text aus dem Text selbst und dem Ergebnis des Aufrufs des Blocks selbst. Wenn die Zahl kleiner ist als Eins, dann gibt der Block einfach den übergebenen Text zurück. Aber schauen wir uns dies einmal konkret an einem Beispiel an.

Repetitions = 3: Der Block ruft sich selbst auf und verbindet das Ergebnis dieses Aufrufs mit der übergebenen Mitteilung. Damit dies funktioniert, muss zuerst der Aufruf bearbeitet werden.

Repetition = 2: Der Block ruft sich selbst auf und verbindet das Ergebnis dieses Aufrufs mit der übergebenen Mitteilung. Damit dies funktioniert, muss zuerst der Aufruf bearbeitet werden.

Repetitions = 1: Der Block übergibt die übermittelte Botschaft. Diese besteht aus der Botschaft und dem Ergebnis der Selbstaufrufe, also Botschaft (und Botschaft (und Botschaft)).

Wir können uns dies auch noch einmal im Programm selbst anschauen, wenn wir dieses Schritt für Schritt abarbeiten: