In the previous section we looked at some problems that were easy to solve using recursion; however, it can still be difficult to find a mental model or a way of visualizing what is happening in a recursive function. This can make recursion difficult for people to grasp. In this section we will look at a couple of examples of using recursion to draw some interesting pictures. As you watch these pictures take shape you will get some new insight into the recursive process that may be helpful in cementing your understanding of recursion.
The tool we will use for our illustrations is called turtle graphics. You will need to put the World.java and Turtle.java classes in the same directory as your Java programs for these examples. Here is the metaphor that turtle graphics uses: You can create a turtle and the turtle can move forward, move backward, turn left, turn right, etc. The turtle can have its tail up or down. When the turtle’s tail is down and the turtle moves, it draws a line as it moves. To increase the artistic value of the turtle, you can change the width of the tail as well as the color of the ink the tail is dipped in.
Here is an example to illustrate some turtle graphics basics. We will use the World and Turtle module to draw a spiral recursively. Listing 4.7.1 shows how it is done. In line 4, we create a world (that is, a winow) for the turtle to draw in, and then we create a new turtle within that world on line 5.
When you run the program, you see the turtle’s movement. Line 7 sets the time (in seconds) between turtle commands. Line 8 makes the window visible. Then, in line 9, we call the drawSpiral method. Finally, in line 10, we hide the image of the turtle so we can see the drawing in its entirety.
Now let us turn our attention to the drawSpiral method. The base case for this simple function is when the length of the line we want to draw, as given by the lineLength parameter, is reduced to zero or less. If the length of the line is longer than zero, we instruct the turtle to go forward by lineLength units and then turn right 90 degrees. The recursive step is when we call drawSpiral again with a reduced length.
public class TurtleSpiral {
public static void main(String[] args)
{
World habitat = new World(300, 300);
Turtle yertle = new Turtle(habitat);
yertle.setDelay(0.1);
habitat.setVisible(true);
drawSpiral(yertle, 100);
yertle.hide();
}
public static void drawSpiral(Turtle myTurtle, int lineLength) {
if (lineLength > 0) {
myTurtle.forward(lineLength);
myTurtle.turnRight(90);
drawSpiral(myTurtle, lineLength - 5);
}
}
}
Listing4.7.1.Drawing a Recursive Spiral using Turtle
That is really about all the turtle graphics you need to know in order to make some pretty impressive drawings. For our next program we will turn to fractals. Fractals come from a branch of mathematics, and have much in common with recursion. By definition, a fractal has the same basic shape no matter how much you magnify it. Some examples from nature are the coastlines of continents, snowflakes, mountains, and even trees or shrubs. The fractal nature of many of these natural phenomena makes it possible for programmers to generate very realistic looking scenery for computer-generated movies. In our next example we will generate a fractal tree.
To understand how this is going to work it is helpful to think of how we might describe a tree using a fractal vocabulary. Remember that we said above that a fractal is something that looks the same at all different levels of magnification. If we translate this to trees and shrubs, we might say that even a small twig has the same shape and characteristics as a whole tree. Using this idea we could say that a tree is a trunk, with a smaller tree going off to the right and another smaller tree going off to the left. If you think of this definition recursively, it means that we will apply the recursive definition of a tree to both of the smaller left and right trees.
Let’s translate this idea to some Java code. Listing 4.7.3 shows how we can use our turtle to generate a fractal tree. Let’s look at the code a bit more closely. You will see that on lines 5 and 7 we are making a recursive call. On line 5 we make the recursive call right after the turtle turns to the right by 20 degrees; this is the right tree mentioned above. Then in line 7 the turtle makes another recursive call, but this time after turning left by 40 degrees. The reason the turtle must turn left by 40 degrees is that it needs to undo the original 20-degree turn to the right and then do an additional 20-degree turn to the left in order to draw the left tree. Also notice that each time we make a recursive call to tree we subtract some amount from the branchLen parameter; this is to make sure that the recursive trees get smaller and smaller. You should also recognize the initial if statement on line 2 as a check for the base case of branchLen getting too small.
The complete program for this tree example is shown in Listing 4.7.4. Before you run the code think about how you expect to see the tree take shape. Look at the recursive calls and think about how this tree will unfold. Will it be drawn symmetrically with the right and left halves of the tree taking shape simultaneously? Will it be drawn right side first then left side?
import java.awt.Color;
public class FractalTree {
public static void main(String[] args)
{
World habitat = new World(300, 300);
Turtle t = new Turtle(habitat);
final Color DARK_GREEN = new Color(0, 128, 0);
t.setDelay(0.1);
t.turnLeft(90);
t.penUp(); // do not draw a trace
t.backward(100);
t.penDown();
t.setColor(DARK_GREEN);
drawTree(75, t);
}
public static void drawTree(int branchLen, Turtle t) {
if (branchLen > 5) {
t.forward(branchLen);
t.turnRight(20);
drawTree(branchLen - 15, t);
t.turnLeft(40);
drawTree(branchLen - 15, t);
t.turnRight(20);
t.backward(branchLen);
}
}
}
Listing4.7.4.Recursively Drawing a Tree
Notice how each branch point on the tree corresponds to a recursive call, and notice how the tree is drawn to the right all the way down to its shortest twig. You can see this in Figure 4.7.5. Now, notice how the program works its way back up the trunk until the entire right side of the tree is drawn. You can see the right half of the tree in Figure 4.7.6. Then the left side of the tree is drawn, but not by going as far out to the left as possible. Rather, once again the entire right side of the left tree is drawn until we finally make our way out to the smallest twig on the left, shown in Figure 4.7.7.
Figure4.7.5.The Beginning of a Fractal Tree
Figure4.7.6.The First Half of the Tree
Figure4.7.7.The Completed Tree
This basic tree program is just a starting point for you, and you will notice that the tree does not look particularly realistic because nature is just not as symmetrical as a computer program. The exercises at the end of the chapter will give you some ideas for how to explore some interesting options to make your tree look more realistic.
Note4.7.8.Java Note.
In line 1 of Listing 4.7.4, we import java.awt.Color (“awt” stands for “Abstract Windowing Toolkit”, one of Java’s basic graphics modules). This class lets us create customized colors. On line 9, we create a new color by giving its red, green, and blue components on a scale of 0 (none) to 255 (all). Our color will have no red, 50% green, and no blue. This results in a dark green. You can also specify the red, green, and blue components as integers on a scale of 0 to 255.
ExercisesExercises
1.Self Check.
Modify the recursive tree program using one or all of the following ideas:
Modify the thickness of the branches so that as the branch_len gets smaller, the line gets thinner. (Use the setPenWidth method. Its parameter gives the width of the line in pixels, and is a double.)
Modify the color of the branches so that as the branch_len gets very short it is colored like a leaf.
Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example choose the angle between 15 and 45 degrees. Play around to see what looks good.
Modify the branchLen recursively so that instead of always subtracting the same amount you subtract a random amount in some range.
