Let's next look at the case of building interesting pictures using recursion. Our first project will be to draw nested squares. The idea is that we will draw successively smaller squares, each of which has sides 4 pixels smaller than the previous square. To keep the squares centered, we will need to shift the upper left-hand corner down and to the right by 2 pixels each time.
We can describe this process recursively as follows. Draw a framed rectangle at position (x,y) with side of length size. Then shift down and to the right by 2 pixels, decrease the size by 4 pixels, and draw the rest of the nested squares starting there.
Here is a Java class doing exactly that:
public class NestedSquares {
private static final double SHIFT = 2;
public NestedSquares(double x, double y, double size,
DrawingCanvas canvas) {
new FramedRect( x, y, size, size, canvas );
if ( size >= 4 ) {
new NestedSquares(x+SHIFT, y+SHIFT,
size-2*SHIFT, canvas);
}
}
The constructor will draw nested squares only if the size of the nested square would be non-negative.
Of course, you could probably figure out how to do the same thing with a while loop:
public class NestedSquares {
private static final double SHIFT = 2;
public NestedSquares(double x, double y, double size,
DrawingCanvas canvas) {
new FramedRect( x, y, size, size, canvas );
while (size >= 4 ) {
size = size -2*SHIFT;
x = x + SHIFT;
y = y + SHIFT;
new FramedRect( x, y, size, size, canvas );
}
}
Now let's make things a bit more interesting. Suppose that we want to be able to move the nested squares in the same way we do a filled or framed rectangle. That is easy to do with this recursive version as long as we have names for the objects we create:
public class NestedSquares {
private static final double SHIFT = 2;
private FramedRect outerSquare;
private NestedSquares rest;
public NestedSquares(double x, double y, double size,
DrawingCanvas canvas) {
outerSquare = new FramedRect( x, y, size, size, canvas );
if ( size >= 4 ) {
rest = new NestedSquares(x+SHIFT, y+SHIFT,
size-2*SHIFT, canvas);
}
}
public void moveTo(double x, double y) {
outerSquare.moveTo(x,y);
if (rest != null) {
rest.moveTo(x+SHIFT, y+SHIFT);
}
}
}
The only change we have made to the constructor is to give names to the square (now called outerSquare) and the rest of the nested squares, rest. The reason for this is so that we can refer to them in the moveTo method.
Notice that the type of rest is NestedSquares. Java has no problem with an instance variable whose type is the same as the entire class. When a class has an instance variable with the same type as the class, we say that it represents a recursive data structure.
The moveTo method is very straightforward. Simply move outerSquare to the desired position, and then move rest to a position two pixels to the right and down so that they will remain properly nested. Other methods like setColor, move, removeFromCanvas would be written similarly.
The basic idea is this: since we have a recursive data structure, methods manipulating it will also be recursive. In this case, we have taken care of the non-recursive part (outerSquare) and then send a recursive message to the rest.
Demo of NestedSquares
How could you do this if you didn't want to do it recursively? If you were to use a while loop you would need to save the names of all of the squares! We'll see later in the semester that this can be a perfectly reasonable solution, but it's certainly more complex than our recursive solution.