Das Programm soll zeigen, wie man auch in einer Sprache wie Assembler eine Rekursion programmieren kann. Dazu habe ich als anschauliches Beispiel ein Labyrinth gewählt. Wollen wir zuerst klären, was Rekursion bedeutet.

Als Rekursion wird der Aufruf eines Unterprogramms /einerProcedure aus sich selbst heraus bezeichnet, ohne daß dabei bestimmte Variablen überschrieben werden. Diese Variablen heißen lokale Variablen. In der Praxis sieht eine Rekursion folgendermaßen aus:

Damit lokale Variablen nicht überschrieben werden, werden sie entweder gleich bei der Deklaration auf dem Stack untergebracht, oder vor einem rekursiven Aufruf werden die Variablen auf den Stack gerettet und bei der Rückkehr wieder von dort geladen. Diese Methode wird in diesem Programm praktiziert.

Nun zu dem Programm selber. Das Prinzip des Programms ist relativ einfach, aber zugegebenermaßen nicht sehr einfach zu verstehen, wie es übrigens bei den meisten rekursiven Programmen der Fall ist.

Das Prinzip

Das Programm arbeitet ähnlich einem Maulwurf. Er gräbt in eine zufällig gewählte Richtung. Wenn er bemerkt, dort geht es nicht weiter, versucht er die anderen Richtungen. Wenn es auch dort nicht weitergeht (auf gut deutsch, wenn er eingeklemmt ist), läuft er zurück. Dieses anschauliche Beispiel kann ohne weiteres auf den Computer übertragen werden. Man geht von einem Startpunkt A aus und sucht einen Zielpunkt B. der so gelegen ist, daß nichts zwischen diesen beiden Punkten A und B ist. Ist B ein gesuchter Punkt, wird die aktuelle Position A gespeichert (lokale Variable auf Stack gelegt). B wird nun der neue Startpunkt A, und die Procedure beginnt von vorne. Angenommen, es gibt von A aus keinen weiteren Punkt B. Dann muß zurückgesprungen werden. Der alte Punkt A wird vom Stack geholt und wieder aktueller Startpunkt. Wenn das Labyrinth fertig gezeichnet, also alles versperrt ist, hat der Startpunkt A wieder die Ausgangskoordinaten.

Das Suchen eines Punktes B erfolgt über die 4 Richtungen. Der Abstand zwischen A und B hat jeweils in die Horizontale und Vertikale einen konstanten Wert. Zwischen A und B wird die Farbe aller Punkte ermittelt. Wenn die Farbe ungleich Null ist, ist der Weg versperrt. Ein Zähler für die getesteten Richtungen wird dekrementiert und eine neue Richtung gesucht. Hat der Zähler den Wert Null, geht es von dieser Position aus nicht weiter, und es erfolgt ein Rücksprung.

Natürlich soll eine Richtung nicht mehrmals getestet werden. Zu diesem Zweck richtet man ein Array ein, in dem man vermerkt, wo schon getestet wurde. Dieses muß selbstverständlich wieder gelöscht werden, wenn ein Punkt B gefunden wurde und die Routine wieder aufgerufen wird.

Nun zum Testen selber. Um alle Punkte zwischen A und B zu testen, werden zwei ineinander verschachtelte Schleifen verwendet. Eine Schleife behandelt die x-, die andere die y-Koordinaten. Da immer vom Startpunkt A aus gerechnet wird, müssen die Step-Werte für die beiden Schleifen ermittelt werden. Es gibt die Step-Werte + 1, 0, -1. Eine Schleife hat immer den Step-Wert 0. Mit den verschachtelten Schleifen läßt sich eine Fallunterscheidung für die getrennte Bearbeitung in x- und y-Richtung vermeiden.

Michael Krusemark