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.

‚***********************************************
'* Rekursionen 
'* in
'* OMIKRON-Basic 
'*
'* Ulrich Hirschmann
'*
'*@ 02.1990,
'*(c) MAXON Computer GmbH 1990
'***********************************************
Init
'
REPEAT
    L_Input(0,0,"Parameter eingeben :",W%L)
    I%L(0)=0:L_Wa%L=0
    PRINT @(2,0);"Ende: Winkel>90 oder [Help]"
    CLS
    Sety%L=250 
    Setx%L=250
    ' Zweige(0,50,W)'       alternativ ********
    Schnee(0,50,W%L)'                  ********

    ' Show'         *** LOGO-Demo ***
    WHILE MOUSEBUT =0: WEND 
    IF MOUSEBUT =2 THEN HCOPY 
UNTIL Immer%L
'
END
'************** Logoprogramm ****************
DEF PROC Show
    FILL STYLE =1,0 
    Pe
    Sety%L=200 
    PRINT CHR$(27);"p"
    WHILE 1
        Setx%L=600 
        Rt(0):Fd(0)
        L_Wa%L=0
        INPUT @(0,0);"Winkel :";I%L 
        PBOX 0,0 TO 640,400 
        Rechtecke(0,6,I%L)
    WEND
    Pd
    PRINT CHR$(27);"q"
RETURN
DEF PROC Quadrat(St%L)
    FOR I%L=1 TO 4
        Fd(St%L):Rt(90) ' **mit rt(33) probieren 
    NEXT I%L
RETURN
DEF PROC Rechtecke(Eb%L,S!(Eb%L),N%L(Eb%L))
    IF S!(Eb%L)>200 THEN RETURN 
    Lt(N%L(Eb%L))
    Quadrat(S!(Eb%L))
    Setx%L=Setx%L-4
    Rec Up'             *** nächste Ebene
    Rechtecke(Eb%L,S!(Eb%L-1)+3,N%L(Eb%L-l)) 
    Rec_Down'           *** und zurück
    Lt(N%L(Eb%L))
    Quadrat(S!(Eb%L))
    Setx%L=Setx%L-4
RETURN
DEF PROC Schnee(Eb%L,S!(Eb%L),N%L(Eb%L))
    '*** Eb setzt den Rekursionszähler zurück 
    IF S!(Eb%L)<4 THEN RETURN   ' *** Abbruch
    WHILE I%L(Eb%L)<N%L(Eb%L)'    *** Anzahl der gezeichneten Radien
        Fd(S!(Eb%L))
        Rec Up'                   *** nächste Ebene
        Schnee(Eb%L,S!(Eb%L-1)/2,N%L(Eb%L-1)) 
        Rec_Down'                 *** und zurück
        Bk(S!(Eb%L))
        Rt(360/N%L(Eb%L))
    WEND
RETURN
'
DEF PROC Zweige(Eb%L,S!(Eb%L),N%L(Eb%L))
    IF S!(Eb%L)<10 THEN RETURN ' *** minimale Streckenlänge
    Lt(N%L(Eb%L)):Fd(S!(Eb%L))
    Rec_Up
    Zweige(Eb%L,S!(Eb%L-1)/1.2,N%L(Eb%L-1))
    Rec_Down
    Bk(S!(Eb%L))
    Rt(N%L(Eb%L)*2):Fd(S!(Eb%L))
    Rec_Up
    Zweige(Eb%L,S!(Eb%L-1)/1.2,N%L(Eb%L-1)) 
    Rec_Down
    Bk(S!(Eb%L)):Lt(N%L(Eb%L))
RETURN
'
'*********************************************** 
'*********** Logobefehlsdefinitionen *********** 
'***********************************************
'
DEF PROC L_Input(L_X%L,L_Y%L,L_Text$,R W%L)
    PRINT CHR$(27);"e"
    -J: INPUT @(L_X%L,L_Y%L);L_Text$;W%L
    IF W%L=0 THEN GOTO -J%L 
    PRINT CHR$(27);"f"
RETURN
DEF PROC Warte: WHILE INKEY$ ="": WEND : RETURN 
DEF PROC Rec_Up:Eb%L=Eb%L+1:I%L(Eb%L)=0: RETURN 
DEF PROC Rec_Down:Eb%L=Eb%L-1:I%L(Eb%L)=I%L(Eb%L)+1: RETURN
DEF PROC Pu: LINE COLOR =0: RETURN ' *** Pen up
DEF PROC Pd: LINE COLOR =1: RETURN ' *** Pen dn
DEF PROC Px: MODE =3: RETURN ' *** Pen XOR
DEF PROC Pe: MODE =1: LINE COLOR =0: RETURN ' *** Pen erease
'
DEF PROC Init
    ON HELP GOSUB L_Ende
    CLS : DEG : PRINT CHR$(27);"f": CLIP 0,0,640,400
    Rt(0):Fd(0)
    DIM Eb%L(999),I%L(999),S!(999),N%L(999)
    MODE =1:Pd 
RETURN
'
-L_Ende: END
'
DEF PROC Rt(Winkel%L)'              *** right turn
    L_W1%L=Winkel%L+L_Wa%L 
    L_Wa%L=L_W1%L 
    L_W%L=L_W1%L-90 
RETURN
'
DEF PROC Lt(Winkel%L)'              *** left turn
    L_W1%L=-Winkel%L+L_Wa%L 
    L_Wa%L=L_W1%L 
    L_W%L=L_W1%L-90 
RETURN
'
DEF PROC Fd(Strecke%L)'             *** forward
    X1%L=Setx%L:Y1%L=Sety%L 
    X2%L=Strecke%L* COS(L_W%L)+Setx%L 
    Y2%L=Strecke%L* SIN(L_W%L)+Sety%L 
    DRAW X1%L,Y1%L TO X2%L,Y2%L 
    Setx%L=X2%L:Sety%L=Y2%L
RETURN
'
DEF PROC Bk(Strecke%L)'             *** backward
    Setxb%L=Setx%L:Setyb%L=Sety%L 
    X1%L=Setxb%L:Y1%L=Setyb%L
    X2%L=Strecke%L* COS(L_W%L-180)+Setxb%L 
    Y2%L=Strecke%L* SIN(L_W%L-180)+Setyb%L 
    DRAW X1%L,Y1%L TO X2%L,Y2%L 
    Setxb%L=X2%L:Setyb%L=Y2%L 
    Setx%L=X2%L:Sety%L=Y2%L 
RETURN