Nicht nur Zahlenfolgen lassen sich rekursiv definieren, auch mit Kurven/Figuren lässt sich das Konzept der Rekursion sehr gut veranschaulichen.

Dabei gibt es im Bereich der rekursiven Kurven einige spezielle Begriffe:

  • Initiator: das Grundgebilde, die Rekursionsbasis
  • Generator: der Rekursionsschritt
  • Rekursionstiefe: Anzahl der Rekursionsebenen / die Genauigkeit der Zeichnung

Wichtig: Im Generator ersetzt man jede Strecke, man kann nicht aus Faulheit aus einer Strecke zwei machen.
(Den Fehler habe ich in der Klausur gemacht 😅 )

Kochkurve

Die Koch-Kurve wurde 1904 von dem schwedischen Mathematiker Helge von Koch veröffentlicht. Der Initiator ist eine simple Linie, der Generator ein stachelähnliches Gebilde aus vier Elementen tieferer Rekursionsebenen.

Kochkurve Beispiel

Code

void koch(int t, double laenge) {
  if (t == 1) {
    zeichneStrich(laenge);
    return;
  }

  koch(t - 1, laenge / 3);
  drehe(60);
  koch(t - 1, laenge / 3);
  drehe(2 * 60 * -1);
  koch(t - 1, laenge / 3);
  drehe(60);
  koch(t - 1, laenge / 3);
}

Die Kurven werden hier von einer Turtle gezeichnet - mehr oder minder ein Stift, der drei Befehle kennt:

  • Bewege dich Vorwärts
  • Drehe dich
  • Hebe/Senke den Stift

Damit kann man (rasterbasierte) Bilder perfekt zeichnen.

Das eigentliche Zeichnen geschieht in Zeile 4 durch zeichneStrich(laenge) - wie genau dieser Befehl lautet, hängt von der genauen Implementierung der verwendeten Turtle ab. Mit drehe() wird die Turtle gedreht.

Dabei dreht man einmal 60° nach links, dann 2 mal 60° nach rechts (26012 \cdot 60^\circ \cdot -1), und dann wieder 60° nach links.

Koch’sche Schneeflocke

Die Koch’sche Schneeflocke ist ein Gebilde aus 3 Kochkurven, die jeweils um 120° gedreht wurden.

Schneeflocke Beispiel

Drachenkurve

Die Drachenkurve ist ein anderes Fraktal, welches sich durch rechte Winkel und ein drachenähnliches Erscheinen auszeichnet.

Ihre Vorschrift lautet wie folgt:
Zeichne die Drachenkurve der tieferen Rekursionsebene, drehe dich um 90 Grad und zeichne eine weitere Drachenkurve der tieferen Rekursionsebene - diese allerdings gespiegelt.

Drachenkurve Beispiel

Pseudocode

Initiator: zeichne Strich
Generator:
  t - 1 zeichnen
  90° links drehen
  t - 1 gespiegelt zeichnen

Implementierung

void drachen(int t, int vz, int laenge) {
  if (t == 0) {
    zeichneStrich(laenge);
    return;
  }

  drachen(t - 1, 1, laenge);
  drehe(90 * vz);
  drachen(t - 1, -1, laenge);
}

Zeile 2-5 sind der Initiator:
Es wird ein Strich der angegebenen Länge gezeichnet.

Zeile 7-9 sind der Generator:
Es wird der Drachen einer Rekursionsebene tiefer gezeichnet, dann wird um 90 Grad gedreht - ob links oder rechts, entscheidet vz. Dann wird noch ein Drachen gezeichnet, diesmal mit negativen Vorzeichen.

Das Vorzeichen vz muss immer mitgegeben werden, damit die einzelnen Figuren richtig gespiegelt werden.

Pythagoras Baum

Der Pythagoräische Baum entstammt - entgegen dem Namen - nicht der Feder Pythagoras, sondern visualisiert seinen berühmten Satz. Ein solcher Baum besteht aus ganz vielen kleinen ‘Häusern’ (im Bild blau/rot) deren Dach die Grundfläche zweier weiterer Häuser bildet.

Beispiel Pythagoras

Implementierung

void pythagorasBaum(int t, int vz, double laenge) {
  if (t == 0) return; // Basis

  // 1. Seite
  turtle.forward(laenge);
  
  // 1. Haus
  turtle.left(angle * vz);
  pythagorasBaum(t - 1, vz, neueLaenge(laenge, angle));
  turtle.right(angle * vz);

  // Obere Seite
  turtle.right(90 * vz);
  turtle.forward(laenge);

  // 2. Haus
  turtle.left(angle * vz);
  pythagorasBaum(t - 1, vz * -1, neueLaenge(laenge, angle);
  turtle.right(angle * vz);

  // 2. Seite
  turtle.right(90 * vz);
  turtle.forward(laenge);

  // Untere Seite
  turtle.right(90 * vz);
  turtle.forward(laenge);

  // Zurück drehen
  turtle.right(90 * vz);
}

Andere bekannte Fraktale

Mandelbrotmenge

Mandelbrotmenge

Sierpinski Dreieck

Sierpinski Dreieck

Juliamenge

Juliamenge

Coole Websites

Ursprünglich hatte ich vor, hier ein paar interessante Skripte einzubinden, die Fraktale erzeugen. Da diese allerdings sehr rechenintensiv sind, habe ich mich dagegen entschieden - schau sie dir besser unter diesen Links an:

Quellcode

Mein Quellcode ist einsehbar unter github.com/Skn0tt/lkAlgorithmik/tree/master/Kochkurven.