Lecture 37

Announcements

Talking Points

Recursion!

Turtle Trees

We'll need our old friends Turtle.java and World.java.

A branch is a stick with two smaller branches on its end

To draw a branch, a turtle should

• Move forward along the stick

• Draw one smaller branch

• Draw the other smaller branch

• Move back to the base of the branch

Why is it important to move back?

public static void tree(Turtle t, int branchesLeftToDo) {
    if (branchesLeftToDo < 1) {
        // draw a "leaf"
        t.forward(10);
        t.backward(10);
    } else {
        // draw a stick
        t.forward(20);
        // draw two more trees
        t.left(35);
        tree(t, branchesLeftToDo - 1);
        t.right(70);
        tree(t, branchesLeftToDo - 1);
        t.left(35);
        // back up
        t.backward(20);
    }
}

The recursive tree is a rewrite-rule fractal or L-system, one of the most common kinds of recursive fractals.

The re-write rule for the tree is:

The left side of this diagram shows a single method invocation and the right side shows what it should do: draw a line and make two more method invocations. The base case is to draw just a line.

Because both the left and right branches have the same starting point in tree, it is important to back up to where we began before each method invocation ends. This is not true of the following two fractals: because the second piece starts where the first ended, the turtle should not back up.

The Koch Snowflake

Note that unlike the tree where branching angles are pretty arbitrary, the angles matter here: to work nicely, 60° and 120° turns are needed.

public static void koch(Turtle t, double lengthOfArrow) {
    if (lengthOfArrow < 3) {
            // draw the arrow itself
        t.forward(lengthOfArrow);
    } else {
            // draw the arrow as four smaller arrows
        koch(t, lengthOfArrow / 3);
        t.right(60);
        koch(t, lengthOfArrow / 3);
        t.left(120);
        koch(t, lengthOfArrow / 3);
        t.right(60);
        koch(t, lengthOfArrow / 3);
    }
}

The dragon curve

Note there are two different rules: one for blue edges and one for red ones. The dragon curve assumes 45° at the two ends, 90° in the middle.

public static void redDragon(Turtle t, double length) {
    if (length < 2) {
        t.forward(length);
    } else {
        t.right(45);
        redDragon(t, 0.7071*length);
        t.left(90);
        blueDragon(t, 0.7071*length);
        t.right(45);
    }
}
public static void blueDragon(Turtle t, double length) {
    if (length < 2) {
        t.forward(length);
    } else {
        t.left(45);
        redDragon(t, 0.7071*length);
        t.right(90);
        blueDragon(t, 0.7071*length);
        t.left(45);
    }
}

The Sierpinski triangle

The angle here is 60°

Sometimes these rules are written textually, like so:

A → B − A − B
B → A + B + A
Base case: draw a line
Angle: 60°

The + or − mean to turn left or right, respectively.

The Hilbert curve

A → − B F + A F A + F B −
B → + A F − B F B − F A +
F means go forward
Base case: do nothing
Angle: 90°

We can turn this into an image, but it isn't as easy since the base case is not draw a line