5 Rekursion, grafisch
Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel



Beim QuickSort-Algorithmus haben wir das erste Mal eine Prozedur kennengelernt, die in ihrem Prozedur-Rumpf sich selbst wieder aufruft. Solche Prozeduren (oder Funktionen) heißen rekursiv. Das Programmieren rekursiver Prozeduren ist eine höhere Kunst, weil sich dabei selbst "kleine" Fehler häufig fatal auswirken. Speziell auf einem alten 16-Bit-Betriebssystem wie Windows 3.1 führ(t)en Rekursionsfehler ziemlich sicher zum Totalabsturz. Deshalb ist es nötig, dass man bei solchen Aufgaben sein Programm sehr genau plant.

Mit rekursiven Prozeduren lassen sich sehr ansprechende Grafiken erstellen. Die nebenstehende Zeichnung eines Farns wurde z.B. auf diese Art und Weise erzeugt. Man sieht, dass sich der Stamm in drei Äste verzweigt, von denen sich jeder wieder in 3 Äste verzweigt, von denen sich jeder wieder in drei Äste verzweigt.....

Offenbar muss man aber einer solchen Rekursion irgendwann einen Riegel vorschieben, denn sonst würde dies ohne Ende so weitergehen! Da außerdem die Anzahl der Äste auf jeder "Rekursionsstufe" zunimmt (- im vorliegenden Beispiel wächst sie in jedem Schritt um das Dreifache der schon vorhandenen Zahl! -), würde nach kurzer Zeit der endliche Speicher des Rechners überlaufen.

Wie wird nun ein sauberer Abbruch der Rekursion erreicht? Auf jeder neuen Rekursionsstufe werden die Äste immer etwas kleiner als auf der vorhergehenden. Wenn die zu zeichnenden Äste klein genug sind, dann wird nicht mehr "weiterverzweigt". Die folgende Prozedur enthält den "Zeichenkern" eines Turtle-Grafik-Programms, das die obige Grafik produziert:
In Delphi :
    procedure TForm1.ButtonFarnClick(Sender: TObject);

       procedure farn(len: Double);
         begin
         with Turtle1 do
           If len > 2 then begin
             FD(len);
             LT(25); farn(len*0.5);
             RT(35); farn(len*0.7);
             RT(25); farn(len*0.4);
             LT(35);
             BK(len);
             end
           else begin
             FD(len);
             BK(len);
             end;
           end;

         begin
         With Turtle1 do begin
           CS;
           PU;
           BK(120);
           PD;
           end;
         farn(80);
         end;
Die Click-Prozedur enthält eine lokale, rekursive Prozedur "farn(len: Double)", die die eigentliche Grafik zeichnet. Vor dem Aufruf von "farn(80)" im "Hauptprogramm" der Click-Prozedur wird lediglich der Bildschirm gelöscht und die Startposition sinnvoll gewählt.
In Java :
    private void farn(double len) {
      if (len > 2) {
        t.draw(len);
        t.turn( 25);
        farn(len * 0.5);
        t.turn(-35);
        farn(len * 0.7);
        t.turn(-25);
        farn(len * 0.4);
        t.turn( 35);
        t.draw(-len);
      } else {
        t.draw( len);
        t.draw(-len);
      }
    }

    public void jButton1_ActionPerformed(ActionEvent evt) {
      t.clear();
      t.turn(90);
      t.move(-120);
      farn(80);
    }
Die Click-Prozedur ruft die private rekursive Prozedur "farn(double len)" auf, die die eigentliche Grafik zeichnet. Vor dem Aufruf von "farn(80)" in der Click-Prozedur wird lediglich der Bildschirm gelöscht und die Startposition sinnvoll gewählt.
Beachten Sie, dass die Turtle beim Verlassen der Prozedur "farn()" exakt genau so positioniert ist, wie sie am Anfang der Prozedur stand! Dies ist unbedingt nötig, um Chaos auf dem Bildschirm zu vermeiden!

Wenn die übergebene Länge noch größer als 2 ist, werden die inneren "farn()"-Aufrufe ausgeführt, andernfalls wird nur ein Strich gezeichnet, die Turtle wieder zurückgeführt und die Prozedur verlassen.





Aufgaben:


  1. Erst mal vorsichtig 'rantasten.....:

    Erstellen Sie ein Programm, das mit Hilfe der obigen Click-Prozedur in einer Turtle-Komponente einen Farn zeichnet.

    Ersetzen Sie in der If-Bedingung der "farn()"-Prozedur
          If len > 2 then begin.....end
          if (len > 2) {....... }
    den Wert 2 der Grenze für die übergebene Länge "len" nacheinander durch die Werte 100, 60, 40, 30, 20,.... Machen Sie sich in jedem dieser Fälle genau klar, warum das Programm gerade die jeweils entstehende Zeichnung produziert. Erst wenn Sie dies begriffen haben, sollten Sie den ursprünglichen kleinen Wert (nämlich 2) wieder einsetzen.

    Experimentieren Sie danach mit den Drehwinkeln in der "farn"-Prozedur.
    Verletzen Sie auch mal die Bedingung, dass der Turtle-Zustand "genau" wieder hergestellt wird!
    Können Sie das Bild gezielt beeinflussen, z.B. den Farn nach der anderen Seite neigen, aber etwas weniger als im Original?



  2. Die Koch'sche Kurve:

    Das obige Bild zeigt die berühmte "Koch'sche Kurve". Sie entsteht ebenfalls rekursiv. Die zugrunde- liegende Figur besteht aus 4 gleichlangen Abschnitten, alle auftretenden Winkel sind 60 oder 120 Grad:

    Wenn man nun statt der hier gezeigten Strecken wieder dieselbe Figur (verkleinert!) verwendet, dann erhält man das folgende Bild:

    Machen Sie sich den Zusammenhang zwischen diesen beiden Bildern restlos klar, ehe Sie weiterlesen!

    Und wenn man das nun ein paar mal "ineinander" schachtelt, dann ergibt sich die obige "Koch'sche Kurve". Der Trick ist also: solange die zu zeichnende "Strecke" noch länger als eine bestimmte Grenze ist, ruft die Zeichenprozedur sich selbst vier mal auf; wenn die Streckenlänge die Grenze unterschritten hat, wird stattdessen der obige Streckenzug aus den 4 Strecken gezeichnet.

    Schreiben Sie ein Programm, das die Koch'sche Kurve zeichnet.




  3. Jetzt kommt die Version für die kalten Tage:

    Wenn Sie die Koch'sche Kurve 6 mal auf die Seiten eines regelmäßigen Sechsecks zeichnen, erhalten Sie die "Koch'sche Schneeflocke", die tatsächlich eine gewisse Ähnlichkeit mit einer "echten" Schneeflocke hat. In der Natur sind rekursive Strukturen sogar relativ häufig anzutreffen, wenngleich die Rekursionstiefe dabei meist recht klein ist....




  4. Und hier gibt's Futter für die permanent Unterbeschäftigten:

    Das folgende Bild zeigt den "Baum des Pythagoras". Analysieren Sie das Bild, entwerfen Sie einen rekursiven Zeichenalgorithmus, der diesen Baum produziert, und schreiben Sie ein entsprechendes Programm! Verzichten Sie dabei zunächst mal auf die dekorativen Flächenfüllungen, und konzentrieren Sie sich auf die algorithmischen Probleme. Wenn dann alles stabil läuft, können Sie die Füllungen "nachrüsten", sofern Ihre Turtle-Komponente das "kann". Hinweise dazu finden Sie in der Hilfe zu Ihrer Turtle!

Lösungsvorschlag für die Aufgaben 1, 2 und 4 [Delphi] [Java]





Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel