Rekursion und Dateien

Mit Rekursion wird eine Programmablaufform bezeichnet, bei der sich das Programm resp. eine Prozedur/Funktion bis zum Eintreten einer Abbruchbedingung immer wieder selbst aufruft. Das Gegenteil ist die Iteration, bei der die Prozedur in einer Schleife immer wieder aufgerufen wird. Bei der Rekursion entscheidet die Prozedur sozusagen selbst, ob sie sich selbst nochmal aufrufen möchte, bei der Iteration liegt diese Verantwortung eher in der aufrufenden Schleife.
Mit der Rekursion lassen sich eine Reihe von Problemen recht elegant lösen, es heißt aber auch, dass man jedes durch Rekursion lösbare Problem auch durch Iteration lösen kann.
Die Rekursion findet bspw. bei Sortieralgorithmen Anwendung, der Quicksort-Algorithmus wird häufig rekursiv implementiert. Das Durchlaufen eines Dateisystems (Verzeichnishierarchie) bietet sich ebenfalls für die Rekursion an.

MODEL SMALL,PASCAL
IDEAL
DATASEG
        array db 100 dup (0)
CODESEG
  start:
        STARTUPCODE
          call sort,OFFSET array
        EXITCODE
        ;
        PROC sort near ArrayOfs:word,Anzahl:word     ;ein Byte-Array sortieren
        USES cx,dx
          mov cx,[Anzahl]
          mov dx,[ArrayOfs]                  ;Vorarbeiten
          .
          ;Verarbeitung
          .
          ;Testen der Abbruchbedingung
          je @@procend
          call sort,dx,cx                    ;erneuter Aufruf der Prozedur
          @@procend:
          ret                                ;Rücksprung
        ENDP sort
end start

Rekursive Prozeduren sind als etwas heikel in Hinsicht auf den Stack einzustufen. Da die Stackbereinigung erst mit dem Rücksprung (ret) aus der Prozedur erfolgt, kann es passieren, dass der gesamte Speicher auf dem Stack verbraucht wurde bevor überhaupt der erste Rücksprung erfolgt. Der Verbrauch steigt umso schneller, je mehr Parameter und lokale Variablen die Prozedur verwendet.
Insofern ist bei der rekursiven Programmierung darauf zu achten, dass es immer eine Abbruchbedingung gibt, die auf jeden Fall wirkt. Zusätzlich sollte darauf geachtet werden, dass ausreichend Stack reserviert wurde, damit zum Zeitpunkt des Abbruchs nicht bereits wichtiger Speicher im Codesegment überschrieben wurde.

Einführung

Bei dem in der Folge besprochenen Beispiel wird es darum gehen, alle Zeichen einer Zeichenkette immer wieder so umzusortieren, dass nach und nach alle möglichen Buchstabenkombinationen ermittelt werden. Die Zeichenkette wird dabei über die Kommandozeile als Parameter an das Programm übergeben; die Ergebnisse werden zeilenweise in eine Datei geschrieben.
Die Anzahl der möglichen Ergebnisse entspricht dabei der Fakultät n! der Zeichenkettenlänge, bei 3 Zeichen gibt es 6 Ergebnisse (1*2*3), bei 4 Zeichen schon 24 (1*2*3*4) und bei 5 Zeichen 120. Spätestens hier wird es umständlich, die Kombinationen von Hand zu ermitteln. Bei nur 10 Zeichen gibt es sage und schreibe bereits 3.628.800 Kombinationen. Zeilenweise in eine Datei geschrieben mit je zwei Zeichen für den Zeilenumbruch ergibt das eine Dateigröße von 43.545.600 Byte, mit 13 Zeichen liegt man bereits bei 93 GigaByte (!). Eingedenk dieser Datenmassen und des Zeitaufwandes, machen lange Zeichenketten hier keinen Sinn.
Der Programmnutzen ist wie so oft umstritten, im einfachsten Fall kann das Programm für Schüttelrätsel verwendet werden, wobei hier noch ein Programm über die Ergebnisdatei laufen sollte, um sinnvolle Kombinationen herauszusuchen (5 Zeichen kann man noch im Kopf umstellen, bei 7 Zeichen muss man schon 5040 Zeilen durchgucken).

Der Algorithmus

Zur Verdeutlichung des Sortiervorgangs hier vorab das Ergebnis des Programmlaufs mit den Zeichenketten 'rt' 'art' und 'bart'.

  rt            tr

 art           rta           tar
 atr           rat           tra

bart          artb          rtba          tbar
batr          arbt          rtab          tbra
brta          atbr          rbat          tarb
brat          atrb          rbta          tabr
btar          abrt          ratb          trba
btra          abtr          rabt          trab

Wie Sie an der ersten Zeile sehen, ist bei zwei Zeichen nur ein Vertauschen notwendig.
Bei drei Zeichen wird es komplexer, wobei die Komplexität bei mehr Zeichen auch nicht mehr ansteigt:
Der Sortiervorgang wird immer für Teilzeichenketten durchgeführt. Der Anfangsbuchstabe bleibt immer der gleiche, bis alle Teilzeichenketten neu geordnet sind. Eine Teilzeichenkette wird immer vom Wortanfang + 1 bis Wortende gebildet, beim Wort 'bart' ist die Teilzeichenkette 'art', deren Teilzeichenkette wiederum 'rt' lautet. Die Teilzeichenkettenzerlegung wird so lange fortgesetzt, bis sich eine Kette aus zwei Buchstaben bildet, die wieder nur vertauscht werden müssen. Nachdem die zwei Zeichen ausgetauscht wurden, wird bei der nächstlängeren Zeichenkette der erste Buchstabe ans Ende rotiert und der Austauschvorgang erneut durchgeführt.
Für längere Zeichenketten bleibt das Prinzip das gleiche. In der ersten Spalte für das Wort 'bart' kann man sehr gut alle Fälle des Wortes 'art' erkennen. Bei mehr als zweistelligen Zeichenketten muss man sich immer das Ausgangswort merken, sozusagen das oberste Wort jeder Spalte, da diese Zeichenkette rotiert wird.

Es muss ein Zeichenkettenarray (cc) geben sowie eine Stringvariable (cWort) zur Zwischenspeicherung und eine Variable, die die Gesamtlänge der Zeichenkette aufnimmt. Diese Variablen sind global, da auf sie von verschiedenen Prozeduren zugegriffen wird.
Im Programm werden mehrere Hilfsprozeduren benötigt. Das Zeichenkettenarray, das immer die aktuelle Sortierung enthält, muss in eine Datei geschrieben werden (exportArray). Das Rotieren des ersten Buchstabens an das Arrayende übernimmt rotateLeft. Diese Prozedur muss Start- und Endpunkt der Rotation als Parameter erhalten. Es werden noch Prozeduren zum Kopieren des Zeichenarrayinhalts (cc) in eine andere Zeichenvariable (getWort) sowie zum Kopieren des aktuellen Verarbeitungsstandes in das Zeichenarray (baseFill) benötigt.
In dem Programm wird es eine rekursive Prozedur geben - shuffle. Dieser wird Beginn und Ende der Teilzeichenkette als Parameter übergeben. Sie prüft, ob die Zeichenkette mehr als 3 Zeichen umfasst. Sollte dies der Fall sein, so ruft sie sich selbst mit Beginn + 1 und Ende (neue Teilzeichenkette) auf und rotiert anschließend das Wort.
Shuffle verfügt über eine lokale Stringvariable sowie eine Variable zum Zählen.
Sollten die Zeichenkette genau 3 Zeichen umfassen, so wird erst cc in die lokale Variable kopiert (mittels getWort), anschließend wird cc exportiert (exportArray). Danach folgt das Austauschen der beiden Zeichen und ein erneuter Export. Anschließend wird das Ergebnis der Tauschaktion nach cc kopiert (baseFill) und die Teilzeichenkette in cc rotiert.

Das Hochsprachenprogramm

Das dargestellte Programm ist in Progress Provision 4GL geschrieben, einer Sprache der 4. Generation, die u. a. alle typischen Elemente einer prozeduralen Hochsprache (Datentypisierung, Bedingungen, Schleifenkonstrukte) beinhaltet. Die Programme werden in einer Laufzeitumgebung ausgeführt. Sie werden zu einer Art Byte-Code kompiliert, vergleichbar dem von Java und in gewissen Grenzen plattformneutral. Es handelt sich um ein kommerzielles Produkt und das hier ist keine Werbung.
Die Sprache ist relativ simpel. Variablen müssen vor ihrer Verwendung deklariert werden. Mit EXTENT werden Arrays der angegebenen Länge erzeugt, Vorbelegung der Variablen mit Startwerten ist mit INITIAL möglich. Die Sprache ist nicht case-sensitiv, alles in Großbuchstaben sind Schlüsselworte der Sprache. Es gibt in diesem Fall kein explizites Hauptprogramm wie man das vielleicht von C oder Pascal oder auch von Assembler kennt. Alles was nicht in Prozedurkörpern steht, gehört in der Reihenfolge des Auftretens zum Hauptprogramm.
Prozedurparameter können die Typen INPUT, INPUT-OUTPUT sowie OUTPUT haben. Bei INPUT wird nur eine Kopie des Wertes übergeben - eine Änderung des Wertes in der Prozedur hat keine Auswirkung auf den aktuellen Parameter. Bei den anderen Typen kann der aktuelle Parameter durch die Prozedur manipuliert werden. Damit entsprechen diese Typen den VAR-Parametern von Pascal bzw. den Referenzen und Adressübergaben in C.
Der Datentyp CHARACTER ist zuweisungskompatibel zu ASCIIZ-Strings, es gibt aber keinen Zugriff auf die Implementierung, sprich, auf einzelne Zeichen wird nicht über Arrayoperationen zugegriffen, sondern nur durch String-Funktionen

DEFINE STREAM outs.
DEFINE VARIABLE cc AS CHARACTER EXTENT 20.
DEFINE VARIABLE c AS CHARACTER.
DEFINE VARIABLE cWort AS CHARACTER INITIAL "bart".
DEFINE VARIABLE iLen AS INTEGER.

OUTPUT STREAM outs TO puzzle.txt.              /*Ausgabe in diese Datei*/

iLen = LENGTH(cWort).                          /*Laenge bestimmen*/
RUN baseFill(cWort).                           /*Initialwert nach cc kopieren*/
RUN shuffle(1,iLen).                           /*Verarbeitung beginnen*/

OUTPUT STREAM outs close.                      /*Datei wieder schließen*/

PROCEDURE shuffle:
DEFINE INPUT PARAMETER iStart AS INTEGER.
DEFINE INPUT PARAMETER iEnd AS INTEGER.

DEFINE VARIABLE i AS INTEGER.
DEFINE VARIABLE cAktWort AS CHARACTER.

  IF iEnd - iStart EQ 2 THEN                   /*Zeichenkette 3 Zeichen lang?*/
  DO i = 1 TO 3:                               /*folgenden Code 3mal durchgehen*/
    RUN getWort(OUTPUT cAktWort).              /*cc in lokale Variable sichern*/
    RUN exportArray(iLen).                     /*cc exportieren*/
    c = cc[iEnd].
    cc[iEnd] = cc[iStart + 1].
    cc[iStart + 1] = c.                        /*2 Zeichen austauschen*/
    RUN exportArray(iLen).                     /*cc wieder exportieren*/
    RUN baseFill(cAktWort).                    /*lokale Variable nach cc kopieren*/
    RUN rotateLeft(iStart,iEnd).               /*cc rotieren*/
  END.
  ELSE
  DO i = 1 TO (iEnd - iStart + 1):
    RUN shuffle(iStart + 1,iEnd).              /*rekursiver Aufruf*/
    RUN rotateLeft(iStart,iEnd).               /*cc rotieren*/
  END.
END PROCEDURE.

PROCEDURE getWort:
DEFINE OUTPUT PARAMETER cpWort AS CHARACTER.
DEFINE VARIABLE i AS INTEGER.

  cpWort = "".
  DO i = 1 TO iLen:
    cpWort = cpWort + cc[i].                   /*uebergebene Variable aus cc fuellen*/
  END.
END PROCEDURE.

PROCEDURE rotateLeft:
DEFINE INPUT PARAMETER iStart AS INTEGER.
DEFINE INPUT PARAMETER iEnd AS INTEGER.

DEFINE VARIABLE i AS INTEGER.
DEFINE VARIABLE c AS CHARACTER.

  c = cc[iStart].                              /*erstes Zeichen sichern*/
  DO i = iStart + 1 TO iEnd:                   /*alle anderen Zeichen im Array*/
    cc[i - 1] = cc[i].                         /*um eine Position vorziehen*/
  END.
  cc[iEnd] = c.                                /*gesichertes Zeichen ans Arrayende*/
END PROCEDURE.

PROCEDURE exportArray:
DEF INPUT PARAMETER ipLen AS INTEGER.
DEF VAR i AS INTEGER.

  DO i = 1 TO ipLen:                           /*Array zeichenweise ohne Formatierungen*/
    PUT STREAM outs UNFORMATTED cc[i].         /*in die Datei ausgeben*/
  END.
  PUT STREAM outs UNFORMATTED SKIP.            /*einen Zeilenumbruch anfuegen*/
END PROCEDURE.

PROCEDURE baseFill:
DEFINE INPUT PARAMETER cpWort AS CHARACTER.

DEF VAR I AS INTEGER.
  DO i = 1 TO LENGTH(cpWort):                  /*Array zeichenweise mit dem*/
    cc[i] = SUBSTR(cpWort,i,1).                /*uebergebenen String fuellen*/
  END.
END PROCEDURE.

Das Assemblerprogramm

TITLE Puzzle
MODEL SMALL,PASCAL
P386N
IDEAL
DATASEG
  cc db 20 dup(0)
  cWort db 20 dup (0)
  iLen dw ?
  c db ?
  cName db "puzzle.txt",0                       ;Dateiname
  filehandle dw 0
STACK 400H
CODESEG
start:
  STARTUPCODE
    call getParam
    mov ah,03Ch                                 ;Handle-Datei erstellen
    mov dx,OFFSET cName
    xor cx,cx
    int 21h
    mov ah,03Dh                                 ;Handle-Datei oeffnen
    mov dx,OFFSET cName
    mov al,1                                    ;write-only-Zugriff
    int 21h
    jc progend                                  ;bei Fehlern Programmabbruch
    mov [filehandle],ax
    mov cx,[iLen]
    dec cx
    call shuffle,0,cx
    mov ah,03Eh                                 ;Handle-Datei schlie&szlieg;en
    mov bx,[filehandle]
    int 21h
    progend:
  EXITCODE

  PROC shuffle near @@iStart:word,@@iEnd:word
  LOCAL cAktWort01:word:10
  LOCAL @@c:byte
  USES ax,bx,cx,dx,di,si
    mov cx,[@@iEnd]
    sub cx,[@@iStart]
    cmp cx,2
    je @@innershufflestart
    jmp @@moreshufflestart
    @@innershufflestart:    ;CX = 2
    mov cx,3
    @@innershuffle:
      lea di,[cAktWort01]
      call getWort,ss,di
      call exportArray
      mov si,OFFSET cc
      add si,dx                                 ;SI = ADDR(cc[iEnd])
      mov al,[ss:si]                            ;AL = cc[iEnd]
      mov [@@c],al                              ;@@c = cc[iEnd]
      mov bx,[@@iStart]
      inc bx                                    ;BX = ADDR(cc[iStart + 1])
      mov al,[ss:bx]                            ;AL = cc[iStart + 1]
      mov [ss:si],al                            ;cc[iEnd] = cc[iStart + 1]
      mov al,[@@c]
      mov [ss:bx],al                            ;[cc[iStart + 1] = @@c
      call exportArray
      call baseFill,ss,di                       ;SS:DI = ADDR(cAktWort)
      mov ax,[@@iStart]
      mov dx,[@@iEnd]
      call rotateLeft,ax,dx
      dec cx
      jnz @@innershuffle
      jmp @@procend
    @@moreshufflestart:
      mov cx,[@@iEnd]
      mov dx,cx
      sub cx,[@@iStart]
      inc cx                                    ;i = 1 TO (iEnd - iStart + 1)
      mov ax,[@@iStart]
      mov bx,ax                                 ;iStart sichern
      inc ax                                    ;AX = iStart + 1
    @@moreshuffle:
      call shuffle,ax,dx                        ;RUN shuffle(iStart + 1,iEnd)
      call rotateLeft,bx,dx                     ;RUN rotateLeft(iStart,iEnd)
      dec cx
      jnz @@moreshuffle
    @@procend:
    ret
  ENDP shuffle

  PROC getWort near @@pSeg:word, @@cpWort:word
  USES es,cx,di,si
    mov cx,ds
    mov di,[@@cpWort]                           ;Quellindex laden
    mov es,[@@pSeg]
    mov si,OFFSET cc
    mov cx,[iLen]
    rep movsb
    ret
  ENDP getWort

  PROC getParam near
  uses cx,si,ds,es
    xor cx,cx
    mov cl,[es:80h]                             ;Laenge cmdline inkl. Space
    dec cl                                      ;minus erstes Leerzeichen
    mov [iLen],cx
    mov si,82h                                  ;sollte 1. Zeichen des Param sein
    mov di,OFFSET cc
    push cx si OFFSET cWort                     ;Laenge, Offset und Ziel pushen
    push es ds
    pop es ds                                   ;ES und DS miteinander tauschen
    rep movsb                                   ;Zeichen kopieren
    mov [word es:di],0A0Dh                      ;Zeilenumbruch anfügen
    pop di si cx                                ;Ziel, Offset und Laenge poppen
    rep movsb                                   ;Zeichen kopieren
    ret
  ENDP getParam

  PROC rotateLeft near iStart:word,iEnd:word
  LOCAL @@i:word
  LOCAL @@c:byte
  USES ax,cx,di,si

    mov di,OFFSET cc
    add di,[iStart]
    mov al,[di]
    mov si,di
    inc si                                      ;SI = DI + 1
    mov [@@c],al
    mov cx,[iEnd]
    sub cx,[iStart]
    @@loop:
      mov al,[si]
      mov [di],al
      inc si
      inc di
      dec cx
      jnz @@loop
    mov al,[@@c]
    mov [di],al
    ret
  ENDP rotateLeft

  PROC exportArray near
  USES ax,bx,cx,dx
    mov ah,040h                                 ;Handle-Datei schreiben
    mov bx,[filehandle]
    mov cx,[iLen]
    add cx,2
    mov dx,OFFSET cc
    int 21h
    ret
  ENDP exportArray

  PROC baseFill near @@pSeg:word, cpWort:word
  USES es,cx,di,si
    mov es,[@@pSeg]
    mov di,OFFSET cc
    mov si,[cpWort]                             ;Quellindex laden
    mov cx,[iLen]
    rep movsb
    mov ah,10
    mov al,13
    stosw
    ret
  ENDP baseFill
END start

Anmerkungen zum Programm

Im Assemblerprogramm ist noch die Prozedur getParam dazugekommen. Sie ist dafür verantwortlich, die an das Programm per Kommandozeile übergebenen Parameter auszuwerten, in diesem Fall einfach nur das zu sortierende Wort. Auf eine Fehlerbehandlung im Sinne von fehlendem oder falsch übergebenen Parameter wurde bewusst verzichtet. Um den Sinn der Anweisungen zu verstehen, muss etwas weiter ausgeholt werden.
DOS stellt jedem Programm beim Programmstart einen sogenannten Program Segment Prefix (PSP) voran. Der PSP ist 256 Byte lang, ab Position 128 stehen die dem Programm übergebenen Parameter in Form eines Pascal-Strings, das heißt, an Position 128 steht die Anzahl der weiteren Zeichen. Der PSP beginnt an einer Segmentgrenze. Welches Segment das ist wird dem Programm durch DOS im Register ES übergeben. Dieses Register wird durch STARTUPCODE nicht verändert.
Das Programm geht einfach davon aus, dass das Sortierwort durch genau ein Leerzeichen vom Programmnamen getrennt ist. Nachdem die Länge aus dem PSP nach CX geladen wurde, wird dieses Leerzeichen einfach von CX abgezogen.
Das Sortierwort wird in getParam sowohl in die Variablen cc und cWort kopiert. Für den Befehl movsb müssen die Register DS und ES vertauscht werden.

Dateioperationen unter DOS können in zwei Varianten ablaufen. Die erste und noch aus CP/M-Zeiten stammende Variante sind die sogenannten File Control Blocks, die heute weitestgehend bedeutungslos sind. Die zweite, zu bevorzugende Variante, sind die File Handles. DOS liefert bei bestimmten Funktionen (Datei erzeugen etc) das systemweit eindeutige Handle zurück. Sollten bei den Handle-Dateifunktionen Fehler auftreten, so wird das Carry-Flag gesetzt und AX enthält einen Fehlercode. Ist das CF nicht gesetzt, so steht in AX das Dateihandle.
Das Handle wird bei den Funktionen zum Lesen und Schreiben der Datei benötigt. DOS stellt drei Standardhandles zur Verfügung, auch bekannt als Standard-In, Standard-Out und Error (0..2). Man kann bspw. Daten auf Standard-Out schreiben, die dann auch auf dem Bildschirm erscheinen, aber mit dem Umleitungssymbol > kann man diese Daten in eine Datei umleiten.
Die Fehlerbehandlung im Programm ist für diesen Bereich eher rudimentär. Fragen zu den Dateifunktionen beantwortet am besten die Referenz

Das komplexeste am Assemblerprogramm ist sicherlich die Prozedur shuffle, der Rest sollte relativ leicht zu verstehen sein. Die meiste Konfusion wird dadurch verursacht, dass versucht wurde, möglichst viele Daten in den Registern zu halten und dabei die Voraussetzungen für die verschiedenen Befehle zu schaffen, insbesondere movsb und die Parameter der verschiedenen Hilfsprozeduren und shuffle selbst.
Da die Arrayindizierung in Progress mit Element 1 beginnt, in Assember jedoch mit 0 (Null), muss hier an einigen Stellen noch an den Arrayindizes gedreht werden.

Das Assemblerprogramm ist in der obigen Form wenigstens 18mal schneller als die Progress-Variante, genaue Daten wurden nicht erfasst. Hier ist aber zu beachten, dass auch kompilierter Progress-Code noch interpretiert wird. Ebenso liegen Progress' Stärken weniger bei der Stringverarbeitung als bei der Datenbankarbeit (Progress bietet sehr einfach anzuwendende Möglichkeiten der Datenbankabfrage und Manipulation).

Das Programm bietet noch Optimierungsspielraum. So sollte es ganz unabhängig vom eigentlichen Sortieralgorithmus möglich sein, erst einen Puffer mit verschiedenen Kombinationen zu füllen und diesen Puffer zu exportieren, statt bei jeder Kombination einen Interrupt und Festplattenzugriff auszulösen.