Gödel, Escher, Bach - ein Endloses Geflochtenes Band

Manager denkt sicher hoffnungslos mechanistisch — aber wir illustrieren ja Rekursion in ihrer präzisesten Form.
Pushen, Poppen und Stapel
    Im vorhergehenden Kapitel habe ich einige Grundbegriffe der Rekursivität vorgestellt zumindest so, wie sie die Computerwissenschaftler sehen. Dies sind push, pop und Stapel (oder genauer push-down-stack), und sie sind alle miteinander verwandt. Eingeführt wurden sie in den späten fünfziger Jahren als Bestandteil von IPL, einer der ersten Sprachen für Artifizielle Intelligenz (AI). „Push“ und „pop“ sind wir bereits in dem Dialog begegnet. Ich will mich trotzdem noch etwas darüber verbreiten. Pushen heißt, die Aufgabe, mit der man sich gerade beschäftigt, in der Schwebe lassen, ohne aber dabei zu vergessen, wo man innegehalten hat, und eine neue Aufgabe in Angriff nehmen. Von dieser neuen Aufgabe sagt man, daß sie auf einer „tieferen Stufe“ stehe als die erste. „Poppen“ ist das Umgekehrte; es bedeutet die Operation auf einer Stufe abschließen, und die eine Stufe höher gelegene Operation, genau wo man aufgehört hatte, wieder aufzunehmen.
    Wie aber erinnert man sich genau, wo man sich auf jeder Stufe befand? Die Antwort: man bewahrt die betreffende Information in einem Stapel auf. Ein Stapel ist also einfach eine Tabelle, die uns über Dinge Auskunft gibt wie 1.) wo wir bei jeder unbeendeten Aufgabe stehengeblieben sind (Jargon: „Return-Adresse“), 2.) was man am Punkt der Unterbrechung an einschlägigen Fakten wissen mußte (Jargon: „Bindung der Variablen“). Wenn man zurückpoppt, um eine Aufgabe wieder aufzunehmen, ist es der Stapel, der den Zusammenhang wiederherstellt, so daß man sich nicht verloren vorzukommen braucht. So sagt uns der Stapel im Beispiel mit dem Telefon, wer auf jeder einzelnen Stufe wartet, und wo man im Gespräch war, als es unterbrochen wurde.
    Übrigens rühren die Ausdrücke „push“, „pop“ und „Stapel“ alle von der bildlichen Vorstellung von Tabletts in einem Selbstbedienungsrestaurant her. Im allgemeinen befindet sich eine Art Federung darunter, die dafür sorgt, daß das obere Tablett mehr oder weniger auf gleichbleibender Höhe liegt. Wenn man also ein Tablett auf den Stapel „pusht“, sinkt dieser ein bißchen; und wenn man das Tablett vom Stapel wegnimmt, springt es — pop! — ein bißchen nach oben.
    Ein weiteres Beispiel aus dem täglichen Leben: Wenn man eine Nachrichtensendung hört, geschieht es oft, daß zu einem auswärtigen Korrespondenten umgeschaltet wird: „Wir schalten nun um zu Susi Schwätzer in Rottenburg an der Fulda.“ Nun hat Susi ein Tonband von einem Lokalreporter, der jemanden vor Ort interviewt hat, und nachdem sie etwas über die Hintergründe gesagt hat, spielt sie es ab: „Hier spricht Karl Quassel, am Ort des Geschehens unweit von Rottenburg an der Fulda, wo der große Raubüberfall stattfand, und ich spreche mit ...“ Nun sind wir drei Stufen hinuntergestiegen. Es kann vorkommen, daß der Interviewpartner ebenfalls ein Gespräch vomBand abspielt. Es ist gar nicht so ungewöhnlich, bei Nachrichtensendungen, drei Stufen hinunterzusteigen. Überraschenderweise sind wir uns des zeitweiligen Aussetzens kaum bewußt. Es wird im Unterbewußtsein ohne Schwierigkeiten festgehalten. Wahrscheinlich liegt der Grund, warum das so leicht ist, darin, daß jede Stufe sich von allen anderen im Kolorit so stark unterscheidet. Wären sie sich alle ähnlich, wären wir in kürzester Zeit völlig durcheinander.
    Ein Beispiel für eine kompliziertere Rekursivität ist natürlich unser Dialog. Hier traten Achilles und Herr Schildkröte auf allen verschiedenen Stufen auf. Manchmal lasen sie eine Geschichte, in der sie selbst als Handelnde auftraten. Hier wird unser Verständnis der Vorgänge vielleicht ein bißchen verschwommen, und wir müssen uns sorgfältig konzentrieren, damit wir nicht in Verwirrung geraten: „Also: der wirkliche Achilles und der wirkliche Herr Schildkröte sind immer noch dort oben in Glücksfalls Luftschloß, aber der sekundäre Herr Schildkröte und der sekundäre Achilles sind in einem Escher-Bild — und dann fanden sie das Buch und lasen es; so ist es also der tertiäre Achilles und der tertiäre Herr Schildkröte, die in den Rillen des Kleinen harmonischen Labyrinths umherwandern. Aber halt! Ich habe irgendwo eine Stufe ausgelassen ...“ Man muß einen solchen Stapel im Bewußtsein haben, auf den man zurückgreifen kann, um der Rekursion im Dialog zu folgen (siehe