Turtlegrafik

Rekursionen

Rekursion ist ein Lösungsverfahren, bei dem ein Problem auf das gleichartige, aber etwas vereinfachte Problem zurückgeführt wird. In Java ist eine Methode dann rekursiv, wenn in ihrem Deklarationsteil sie selber aufgerufen wird. Damit sich ein rekursives Programm nicht endlos aufruft, braucht es eine Abbruchbedingung ("Verankerung"). Die Turtlegrafik eignet sich hervorragend für die Programmierung von Rekursionen. Es entstehen dabei sehr schöne Bilder.

Beispiel 1: Das Zeichnen einer Treppe kann iterativ (mit einer while- oder for-Struktur) oder rekursiv programmiert werden. Bei der rekursiver Lösung wird eine Treppe mit 6 Stufen aus einer Stufe und einer Treppe mit 5 Stufen zusammengesetzt, Treppe mit 5 Stufen kann auf eine Stufe und einer Treppe mit 4 Stufen zurückgeführt werden. In der Methode staircase(n) wird jeweils dieselbe Methode staircase(n - 1) aufgerufen, wobei der Parameter bei jedem neuen Aufruf um 1 kleiner wird.. Wenn die Abbruchbedingung n = 0 erfüllt ist, bricht das Programm ab.

// Tu18.java

import ch.aplu.turtle.*;

public class Tu18 extends Turtle
{
  public Tu18()
  {
    staircase(6);
  }

  private void staircase(int n)
  {
    if (n == 0)
      return;

    step();
    staircase(n - 1);
  }

  private void step()
  {
    forward(20);
    right(90);
    forward(20);
    left(90);
  }

  public static void main(String[] args)
  {
    new Tu18();
  }
}

Beispiel 2: Der binäre Baum

Das Problem lässt sich auf diese einfache Grundfigur zurückführen. Die Methode tree() wird jeweils im linken und rechten Ast mit der halben Streckenänge s aufgerufen. Für s < 8 bricht die Rekursion ab.

// Tree.java

import ch.aplu.turtle.*;

public class Tree extends Turtle
{
  public Tree()
  {
    setY(-100);
    tree(128);
  }

  private void tree(int s)
  {
    if (s < 8)
      return;

    forward(s);
    left(45);
    tree(s / 2);
    right(90);
    tree(s / 2);
    left(45);
    back(s);
  }

  public static void main(String[] args)
  {
    new Tree();
  }
}

Beispiel 3: Quadratmuster
Das erste Quadrat hat die Seitenlänge 64. Bei jedem weiteren Aufruf der Methode figure() wird die Seitenlänge halbiert. Die Rekursion bricht ab, wenn s < 1 ist. Ergänzt man die Methode figure() mit folgenden zwei Zeilen
figure(x - s, y - s, s/2);
figure(x + s, y - s, s/2);
so werden Quadrate auch im unteren Bereich gezeichnet. Mit gefüllten Quadraten entsteht ein schönes Teppichmuster.

// SquarePattern.java

import ch.aplu.turtle.*;

public class SquarePattern extends Turtle
{
  public SquarePattern()
  {
    hideTurtle();
    figure(0, 0, 64);
  }

  private void figure(double x, double y, double s)
  {
    if (s < 1)
    {
      return;
    }
    else
    {
      setPos(x - s/2, y - s/2);
      square(s);
      figure(x + s, y + s, s/2);
      figure(x - s, y + s, s/2);
    }
  }

  private void square(double s)
  {
    for(int i = 0; i < 4; i++)
    {
      forward(s);
      right(90);
    }
  }

  public static void main(String[] args)
  {
    new SquarePattern();
  }
}

Beispiel 4: Koch-Kurve
Wie diese Kurve entsteht sieht man, wenn man die Anzahl Generationen auf 1, 2, oder 3 reduziert.

1 Generation 2 Generationen 3 Generationen

// Koch.java

import ch.aplu.turtle.*;

public class Koch extends Turtle
{
  public Koch()
  {
    double length = 200;
    int generations = 4;
    hideTurtle();
    setPos( -180, 0);
    right(90);
    koch(length, generations);
  }

  private void koch(double s, int n)
  {
    if (n == 0)
    {
      forward(s);
      return;
    }
    koch(s / 3, n - 1);
    left(45);
    koch(s / 3, n - 1);
    right(90);
    koch(s / 3, n - 1);
    left(45);
    koch(s / 3, n - 1);
  }

  public static void main(String[] args)
  {
    new Koch();
  }
}

Beispiel 5: Peano

Peano ist eine der bekanntesten Rekursion. Das Problem lässt sich auf eine einfache Figur zurückführen.

// Peano.java
import ch.aplu.turtle.*;

public class Peano extends Turtle
{
  public Peano()
  {
    setPos(185, -185);
    speed(-1);
    peano(6, 6, 90);
  }

  private void peano(int n, int s, int w)
  {
    if (n == 0)
    {
      return;
    }
    lt(w);
    peano(n - 1, s, -w);
    fd(s);
    rt(w);
    peano(n - 1, s, w);
    fd(s);
    peano(n - 1, s, w);
    rt(w);
    fd(s);
    peano(n - 1, s, -w);
    lt(w);
  }

  public static void main(String[] args)
  {
    new Peano();
  }
}

Weitere bekannte Rekursionen:

Sierpi
Spiro
Dragon
Menger
TreeFractal

Aufgaben