There is a close relationship between trees and recursive algorithms. We saw in the previous chapter how recursion can be used to explore and draw various trees and tree-like shapes, and how the
shape of those trees mirrors the way the algorithms operate. In the programs we developed for drawing the Pythagoras tree, for instance, every square of the tree corresponds to a single recursive function call and every branch to an entire cascade of nested function calls. And just as each branch is a
smaller version of the whole tree, the algorithm for drawing each branch is a smaller instance of the algorithm for the whole problem.
All recursive algorithms produce such a tree-like hierarchy of problems and sub-problems. Conversely, being able visualize computational problems as a hierarchy of sub-problems is the key to using recursion effectively. In this chapter we consider a few additional geometric problems whose recursive
nature isn’t quite as obvious.
Figure 4.1 shows a so-called Hilbert curve, a curve that starts in the lower-left corner of the square, ends in the lower-right corner, and visits every point on a \(64\times 64\) grid exactly once. It’s clear that the curve is highly symmetrical and consists of a handful of building
blocks that are repeated in different orientations and arrangements, but if someone told you that the curve has a recursive structure, you would probably have a hard time working out the construction rules from the final shape.
Figure 4.1 Example of a Hilbert curve. The curve starts in the lower-left corner, visits every grid point inside a square, and ends in the lower-right corner.
The Hilbert curve in Fig. 4.1 is just one example from an infinitely large family of curves that are constructed by repeatedly subdividing a simple base shape. This base shape is shown in the left part of Fig. 4.2: it is shaped like an inverted U that visits the corners of a square in clockwise order, starting in the lower-left corner and ending in the lower-right corner. In the first subdivision step, this U-shape is replaced with a more complicated
shape that consists of four smaller U-shapes that are connected by three line segments, as shown in the right part of the figure. The two U-shapes at the bottom of the resulting Y-shape turn counterclockwise and the two at the top turn clockwise. Notice that the new curve visits the four corners of a larger
square in the same order as before and touches every point on a \(4\times 4\) grid.
Figure 4.2 The subdivision scheme behind Hilbert curves. The process starts with a single U-shaped curve that is replaced with four smaller curves of the same form that are connected by three additional lines shown in gray.
The same process can be repeated as many times as desired. In each step, we replace all U-shapes with four appropriately rotated and mirrored Y-shapes. (The subdivision rule for counterclockwise U-shapes can be obtained by reversing the direction of all arrows in Fig. 4.2.) The curve we obtain after \(k\) steps is called a Hilbert curve of order \(k\).
The first few Hilbert curves, scaled down to a common size, are shown in Fig. 4.3. All Hilbert curves start in the lower-left corner, end in the lower-right corner, and visit every point on a \(2^{k+1}\times 2^{k+1}\) grid inside the
square. It’s easy to see that the curves are self-similar in the sense that every quadrant of a Hilbert curve is itself a Hilbert curve of the previous order. For example, the order-3 curve consists of four order-2 curves, each of which consists of four order-1 curves, each of which
consists of four order-0 curves.
Figure 4.3 Hilbert curves of different orders.
Figure 4.3 hints at another unusual property of Hilbert curves: As the order increases, the curve gets longer and coils up ever more tightly inside the square. Mathematically, as the order tends towards infinity, the curve becomes
infinitely long and converges toward the unit square. The Hilbert curve is therefore said to be a space-filling curve, a class of one-dimensional curves that converge toward two-dimensional shapes.
Drawing Hilbert Curves
At the lowest level, every Hilbert curve consists of a sequence of horizontal and vertical line segments of uniform length. We can therefore describe its shape by specifying the curve’s starting point and the list of directions that lead from the start to the end point. For example,
the basic U-shape starts in the lower-left corner and can be drawn by going north, east, and south. Similarly, the first-order curve consists of 15 line segments and can be drawn by going
east, north, west, north
north, east, south, east
north, east, south, south
west, south, east.
The first three directions on each line describe rotated U-shapes that are connected by additional line segments shown in italics. Notice that the connecting lines by themselves form a basic U-shape north-east-south.
How do we represent these directions in a computer program? One option is to define four integer constants called NORTH, EAST, SOUTH, WEST as shown in Listing 4.1. The constants are defined in clockwise order, which allows us to rotate a direction clockwise by incrementing its value (wrapping around to 0 when going above WEST), and counterclockwise by decrementing it (wrapping
around to \(3\) when going below NORTH). Using the modulo operator, we can express both kinds of rotations as follows:
Depending on whether steps is positive or negative, this expression rotates direction one or more steps in either clockwise or counterclockwise order. This operation is implemented by the turn() method defined in the same listing; the floorMod() function is used instead of the modulo operator % to ensure that the expression wraps around correctly when steps is negative.
Listing 4.1ch4 / HilbertCurve
// A class for computing Hilbert curves.
public class HilbertCurve {
// Predefined directions.
static final int NORTH = 0;
static final int EAST = 1;
static final int SOUTH = 2;
static final int WEST = 3;
// Turn the given direction clockwise ('steps' positive)
// or counterclockwise ('steps' negative).
static int turn(int direction, int steps) {
return Math.floorMod(direction + steps, 4);
}
// ...
}
For example, if direction is an integer between 0 and 3, we can construct a clockwise U-shape that starts out in this direction by calling turn() twice to produce a list of three directions:
Now let’s extend this idea to general Hilbert curves. As indicated in Fig. 4.2, a Hilbert curve of order \(k\) consists of four Hilbert curves of order \(k-1\) that are connected using three line segments. A clockwise Hilbert
curve that starts in a given direction can therefore be described recursively as follows:
The same process works for counterclockwise curves, except that directions must be turned in the opposite direction (for instance, \(\Id {direction}+2\) becomes \(\Id {direction}-2\)) and that CCW and CW must be interchanged.
Listing 4.2 shows an implementation of this process. The hilbertCurve() function computes a Hilbert curve of a given
order whose orientation is described by a direction and a rotation that is either \(+1\) for a clockwise shape or \(-1\) for a counterclockwise shape. The function outputs the resulting curve as list of directions: Each of the four recursive calls to hilbertCurve() adds the directions that describe the nested Hilbert curve of lower order to result, and the three calls to add() produce the
short line segments that connect the nested shapes. The two nested curves in the middle have the same starting direction and orientation as the main curve, whereas the two nested curves at either end are rotated and have the opposite orientation.
For example, the Hilbert curve of order \(2\) can be computed by setting off north in clockwise direction and collecting the resulting steps in an array directions:
var directions = new ArrayList<Integer>();
hilbertCurve(2, NORTH, +1, directions);
System.out.println(directions);
which reads east, north, west, north, north, east, south, east, north, east, south, south, west, south, east. As desired, this is the first Hilbert curve in Fig. 4.3.
Exercises
Exercise 4.1.Write a program that prints the coordinates of all points on a Hilbert curve of a given order. For example, the points along the order-1 Hilbert curve might be printed as