Rekursion in OMIKRON.BASIC

Was in anderen Sprachen möglich ist, muss doch auch in BASIC möglich sein. Und mit einem kleinen Trick ist es das auch. Im Rahmen eines LOGO-Seminars kamen die mannigfaltigen Vorzüge von LOGO ZUR Sprache, die es unter anderem erlauben, auf kürzeste Weise rekursive Programme zu schreiben. Dieses sei in einer “Primitivsprache” wie zum Beispiel BASIC nur schwer möglich. Um ähnliche Resultate zu erzielen, müsste man sich in BASIC seitenlanger Programme bedienen.

Diese Auffassung zu widerlegen, war für mich der Anstoß für meinen Versuch in OMIKRON-BASIC. Mit nur zwei weiteren Befehlen läßt sich das Kapitel der Rekursionen auch in BASIC abhandeln. Allerdings verlangt die BASIC-Lösung auch etwas mehr Gedankenaufwand vom Programmierer.

Wie dem Listing zu entnehmen ist. habe ich auf zwei beliebte LOGO-Beispiele zurückgegriffen. Schnee zeichnet, wie der Name schon sagt, Schneekristalle auf den Bildschirm, wobei die Anzahl der Radien variabel ist. Zweige liefert die bekannte Baumstruktur mit variablem Winkel. Und Show liefert interessante Grafiken aus sich drehenden Quadraten. Es sind aber durchaus auch andere Beispiele möglich und relativ leicht selbst zu erstellen.

Die implementierten LOGO-Befehle dienen nur dem Zweck der Demonstration. So treten Rundungsfehler auf, die sich auch nur in einem Demoprogramm vertreten lassen. Aber vielleicht weiß ja jemand bessere Algorithmen?

Da Omikron-BASIC sich nicht um die Verwaltung der Variablen bei Selbstaufrufen von Prozeduren kümmert, müssen wir das eben selbst erledigen. Zu diesem Zweck erhält jeder Aufruf der Prozedur einen eigenen Variablensatz durch den Index Eb. Bei diesem Verfahren ist die Rekursionstiefe nur durch den Speicherplatz begrenzt, da die Variablen als Array definiert sind. Doch nun zur Beschreibung des Listings: Nach der Initialisierung folgt das Hauptprogramm, welches eines der Beispiele aufruft. Der Prozedur Schnee werden folgende Parameter übergeben: Eb - das ist die Zählervariable für die Rekursionsebenen, S(Eb) - bestimmt die Länge der Anfangsstrecke, N(Eb) - die Anzahl der Radien. In der Prozedur Zweige wird durch N(Eb) der Winkel zwischen zwei Ästen übergeben. Die Übergabe des Wertes Null durch Eb beim Start der Prozeduren dient zum Zurücksetzen des Rekursionszählers. Zeile 63 enthält die Abbruchbedingung bei Unterschreiten einer Mindestlänge. In der nächsten Zeile befindet sich die Zählschleife für die Anzahl der zu zeichnenden Radien. Der Befehl Fd(S(Eb)) zeichnet nun eine Gerade mit der Länge S. Ihre Richtung ist vom letzten Aufruf der Prozedur Rt() abhängig, die bei der Initialisierung auf 0 Grad (senkrecht nach oben) gesetzt wurde.

Vor dem Selbstaufruf der Prozedur müssen nun der Rekursionsebenenzähler erhöht und der Schleifenzähler I(Eb) zurückgesetzt werden. Das erledigt die Prozedur Rec_up. Ebenso werden nach dem Selbstaufruf der Ebenenzähler wieder erniedrigt und der Schleifenzähler wieder auf seinen vorigen Wert gebracht (Rec_down). Bis zur Zeile 68 existieren beim Programmablauf lediglich eine bestimmte Anzahl von Schneeprozeduren. die bisher nur eine Gerade gezeichnet und sich dann selbst wieder aufgerufen haben. In Zeile 69 zeichnet zuerst die zuletzt erzeugte Prozedur eine Gerade rückwärts [Bk(S(Eb))], und dann wird ein Winkel nach rechts vollzogen. Durch den Index Eb existiert praktisch für jede Rekursionsebene ein eigener Variablensatz.

Beim Selbstaufruf der Prozedur muß aber auf die bereits wertzugewiesenen Variablen zurückgegriffen werden. Deshalb erfolgt der Aufruf mit S(Eb-1). Die Division durch 2 erniedrigt lediglich kontinuierlich die Streckenlänge. Das Beispiel Zweige schaut da durch den doppelten Selbstaufruf schon wesentlich wilder aus. Die Prozedur Rechtecke verdeutlicht die Wirkungsweise von Rekursionen noch einmal sehr anschaulich. Nur wird hier bei jedem Selbstaufruf die x-Koordinate verringert. Die LOGO-Befehle erklären sich mit ein wenig Trigonometrie von selbst. Nur sei nochmals darauf hingewiesen, daß sie nur für Demonstrationszwecke gedacht sind. Allerdings benötigt man mit diesen Befehlen. z.B. für die beliebte Analoguhr auf dem ST. nur maximal 20 Zeilen. Versuchen lohnt sich! Zum Schluß sei noch darauf hingewiesen, daß es natürlich nicht meine Absicht ist, BASIC als die Hochsprache schlechthin zu verteidigen. Speziell Rekursionen lassen sich mit anders strukturierten Sprachen sicher besser bearbeiten. Aber möglich ist es in BASIC eben doch.