Chapter 3 Growing Trees

Computer programming is the art of solving complex problems by dividing them into smaller pieces that can be solved more easily. In the previous chapter we saw how iteration splits computations into long chains of steps, each of which incrementally builds on the steps that come before it. But not all problems lend themselves to simple iterative solutions. In this chapter we will discuss an alternative approach known as divide-and-conquer, which organizes the steps of an algorithm hierarchically instead of linearly.

3.1 Iteration and Recursion¶

The idea behind the divide-and-conquer method is simple: Instead of trying to solve the problem directly, we first divide it into multiple simpler parts, solve those parts individually, and then combine these results into the solution of the original problem. In many cases, the subdivision step can be repeated: We split a problem into sub-problems, each of which can be split into sub-sub-problems, and so on, until we get something that is so simple that is can be solved without further subdivision. In contrast to the sequence of computational steps used by iterative algorithms, this approach produces a hierarchy of computational steps.

To illustrate this approach, let’s start with the problem of finding the smallest element in a list of \(n\) integers. There is an obvious iterative solution for this problem: loop over the list while keeping track of the smallest element found so far:

public static int minIterative(int[] array) {
    int smallest = Integer.MAX_VALUE;
    for (int element : array)
        smallest = Math.min(smallest, element);
    return smallest;
}

We start by initializing smallest to MAX_VALUE, which is the largest number that can be stored in an int, and then iterate over all elements of array. In each iteration, we update smallest if it is larger than the current element and leave it unchanged otherwise. At the end of the loop, smallest contains the smallest element of array or MAX_VALUE if the array is empty.

While a plain loop is arguably the simplest way to solve the problem, we can also find the smallest element using divide-and-conquer. The idea behind all divide-and-conquer algorithms is to split a problem into multiple smaller problems, solve those sub-problems individually, and then combine the partial results to find the solution of the original problem.

The divide-and-conquer algorithm for finding the smallest number in an array works as follows. First, we split the numbers into two parts. For instance, if the original array is (8, 5, 1, 2, 4, 9, 0), we split this list in the middle into a left half (8, 5, 1, 2) and a right half (4, 9, 0).

We can now search for the smallest element in these two smaller arrays, which gives us 1 for left half and 0 in the right half. The smallest element of the whole list must the smaller of these two partial results, namely 0.

The beauty of the divide-and-conquer method is that it can often be applied repeatedly to divide the original problem into a hierarchy of smaller and smaller sub-problems. To find the smallest number in each of the two halves, for instance, we can split them again to obtain four lists of numbers

and splitting once more gives us six additional elementary lists.

The entire process can be visualized as a tree with the original problem at the root, as shown in the upper part of Fig. 3.1.

The lower part of the figure illustrates how we can find the smallest element of the tree by walking upwards, from the leaves to the root. First, we compare adjacent leaves and move the smaller number to their common ancestor in the tree; this gives us the number 5 for the first pair of leaves, 1 for the second, and 4 for the third. We then compare adjacent numbers in the previous layer of the tree, which gives us 1 for the left half of the tree and 0 for the right. One final comparison then gives us the minimum of the original list, which is 0.

You can think of a divide-and-conquer algorithm as proceeding in two phases: the divide phase builds the tree from the top down by repeatedly subdividing the original problem into smaller, more manageable tasks, and the conquer phase moves in the opposite direction, computing the final solution by working its way up from the leaves to the root.

While it is possible to implement divide-and-conquer methods such as this one using iteration, recursion is usually the simpler and more natural approach. In the following listing, the recursive function minRecursive() computes the smallest element in array in the index range from start to end using the approach we have just described:

public static int minRecursive(int[] array, int start, int end) {
    return switch (end - start) {
        case 0 -> Integer.MAX_VALUE;
        case 1 -> array[start];
        default -> Math.min(
                minRecursive(array, start, (start + end) / 2),
                minRecursive(array, (start + end) / 2, end));
    };
}

If the range is empty, the function returns MAX_VALUE; this can only happen if the original list is empty, since the subdivision process never produces empty ranges. If the range contains a single element array[start] it is returned immediately. Otherwise, if the range contains two or more elements, we split it into two roughly equal halves, call minRecursive() recursively to find the smallest element in each, and use min() to select the smaller of the two results.

Of course, minRecursive() doesn’t actually construct a full tree like the one in Fig. 3.1 explicitly, but its execution follows the same tree-like structure: Every invocation of minRecursive() corresponds to a particular node in the tree, and the call stack at that point represents the path from the root to that node. There is a close relationship between recursion and trees in general: Just as the structure of recursive algorithms can be naturally visualized using trees, most tree-like shapes and data structures are most easily constructed and processed using recursive algorithms.

Despite the obvious differences, iteration and recursion are actually two sides of the same coin: every computation that can be expressed using iteration can also be expressed using recursion and vice versa. It’s not difficult to see why that’s the case: Every loop can be simulated by a recursive function that calls itself for as long as the loop condition is fulfilled, and every recursive algorithm can be simulated by an iterative algorithm by keeping track of recursive calls in a stack-like data structure.

Even though iteration and recursion are equally powerful in theory, there are reasons to prefer one over the other in practice. Iteration often leads to simpler programs if a computation can be expressed as a well-defined sequence of steps, and iterative algorithms tend to run slightly faster since most compilers are better at optimizing loops than recursive function calls. Recursion, on the other hand, excels at problems that branch into multiple sub-problems, and in such cases leads to algorithms that are simpler and easier to prove correct. At the end of the day, both approaches are equally indispensable for expressing repetition in computer programs.

Exercises

[3.1]Write a recursive function that has the same effect as the following for loop:

for (int i = 0; i < 10; i++)
    System.out.println(i):

[3.2]Devise and implement a recursive algorithm for reversing lists.

3.2 Pythagoras Trees¶

As a slightly more complicated example of a recursive shape, consider the Pythagoras tree shown in Fig. 3.2. A Pythagoras tree consists of a square trunk from which two smaller Pythagoras trees branch off to form the boughs and ultimately the leaves of the tree.

The basic building block of the Pythagoras tree is illustrated in Fig. 3.3. It consists of a base square and two attached smaller squares that form a right triangle with an inner angle \(\alpha \). The Pythagorean theorem \(a^2+b^2=c^2\), which relates the areas of the three squares, gives the tree its name. If we assume that the base square has side length 1, the long side of the triangle has length 1 and its two legs have length \(\cos \alpha \) and \(\sin \alpha \), respectively.

We can compute the squares that make up the Pythagoras tree as follows. The idea is to find two sequences of geometric operations, let’s call them BranchL and BranchR, that transform the base square in Fig. 3.3 into the two squares that form the left and right arm. If we transform the resulting two squares again using BranchL and BranchR, we obtain four additional squares, which are the root’s grandchildren in the Pythagoras tree. Every square in the tree can be computed by transforming the root square using a combination of transformation: Starting at the root of the tree and moving toward the desired square, we apply BranchL every time we move to the left and BranchR every time we move to the right.

Here is how these two two transformations look. The left square can be obtained from the base square in three steps:

• 1. Scale the base square by a factor of \(\cos \alpha \) to make it the correct size.

• 2. Rotate the resulting square counterclockwise by the angle \(\alpha \) around its lower-left corner to give it the correct orientation.

• 3. Move it one unit upward so that its lower-left corner ends up at \((0,1)\).

The square that forms the right branch can be constructed similarly:

• 1. Move the base square one unit to the left so that its bottom-right corner coincides with the origin,

• 2. Scale by \(\sin \alpha \).

• 3. Rotate right by \(\pi /2-\alpha \).

• 4. Move the resulting square to the upper-right corner of the base square.

Let’s introduce a few notations for specifying these types of geometric transformations. For a transformation that scales all coordinates by a factor \(a\) we write \(\text {Scale}(a)\); for the transformation that rotates points by an angle \(\phi \) we write \(\text {Rotate}(\phi )\); and for the transformation that shifts points by an amount \(dx\) horizontally and by \(dy\) vertically we write \(\text {Translate}(dx, dy)\). If a sequence of geometric transformations are performed one after another, we write the individual transformations in product form. This lets us we write the transformation \(\text {BranchL}\) that constructs the left branch of the Pythagoras tree by multiplying three individual transformations:

\begin{equation} \label {eq:tleft} \text {BranchL} = \text {Translate}(0,1)\cdot \text {Rotate}(\alpha )\cdot \text {Scale}(\cos \alpha ) \end{equation}

We follow the mathematical convention of writing a sequence of transformations from right to left, so the above definition states that BranchL first applies Scale(), then Rotate(), and finally Translate(). The transformation for the right branch of the Pythagoras tree can be written similarly as a sequence of four geometric transformations:

\begin{equation} \label {eq:tright} \begin{split} \text {BranchR} &= \text {Translate}(1,1)\cdot \text {Rotate}(\pi /2-\alpha )\\ &\quad \cdot \text {Scale}(\sin \alpha )\cdot \text {Translate}(-1,0). \end {split} \end{equation}

Again, the right-hand side must be read from right to left: The right branch is constructed by translating, scaling, rotating, and then translating again.

Geometric Transformations

The three types of geometric transformations we just met — translation, rotation, and scaling — all belong to the class of affine transformations, which you may remember from our discussion of iterated function systems in Section 1.2. An affine transformation is a function that maps points to other points by multiplying them by first a \(2\times 2\) matrix and then adding a vector to the result:

\begin{equation} \vec {p}\quad \mapsto \quad \begin{pmatrix} a & b\\ c & d \end {pmatrix}\vec {p} + \begin{pmatrix} t_x\\t_y \end {pmatrix}. \end{equation}

We already developed a class Affine for working with affine transformations in the previous chapter. The main constructor of Affine takes the six coefficients of the affine transformation as its arguments, so the general transformation above is constructed as follows:

new Affine(a, b, c, d, tx, ty);

We will now discuss how to express the geometric transformations needed to construct the Pythagoras tree as affine transformations and how to extend Affine with methods for constructing them. The four affine transformations we are interested in are illustrated in Fig. 3.4.

Let’s start with a transformation we haven’t mentioned so far but that will turn out to be useful later on: The identity transformation, which maps every point to itself. It’s not hard to see that the only affine transformation that leaves every point unchanged has the following form:

\begin{equation*} \begin{pmatrix} 1 & 0\\ 0 & 1 \end {pmatrix}\vec {p} + \begin{pmatrix} 0\\0 \end {pmatrix}\qquad \text {Identity} \end{equation*}

This transformation first multiplies the point \(\vec {p}\) by the identity matrix \(\bigl (\begin {smallmatrix} 1 & 0\\ 0 & 1 \end {smallmatrix}\bigr )\) and then adds the zero vector \(\bigl (\begin {smallmatrix}0\\0\end {smallmatrix}\bigr )\).

The affine transformations for translation and scaling are simple variations of the identity transformation. A translation moves every point by a certain amount, say \(t_x\) units along the \(x\)-axis and \(t_y\) units along the \(y\)-axis. We can express this as an affine transformation by setting the matrix part to the identity matrix and the translation vector to \(\bigl (\begin {smallmatrix}t_x\\t_y\end {smallmatrix}\bigr )\):

\begin{equation*} \begin{pmatrix} 1 & 0\\ 0 & 1 \end {pmatrix}\vec {p}+ \begin{pmatrix} t_x\\t_y \end {pmatrix}\qquad \text {Translation} \end{equation*}

The scaling transformation multiplies all coordinates by a factor \(a\), which can be expressed as multiplying by a scaled version of the identity matrix followed by adding the zero vector:

\begin{equation*} \begin{pmatrix} a & 0\\ 0 & a \end {pmatrix}\vec {p} + \begin{pmatrix} 0\\0 \end {pmatrix}\qquad \text {Scaling} \end{equation*}

And finally, rotation by an angle \(\phi \) can be achieved by multiplying \(\vec {p}\) with a rotation matrix:

\begin{equation*} \begin{pmatrix} \cos \phi & -\sin \phi \\ \sin \phi & \cos \phi \end {pmatrix}\vec {p} + \begin{pmatrix} 0\\0 \end {pmatrix}\qquad \text {Rotation} \end{equation*}

Listing 3.1 demonstrates how to create Affine objects that implement these four elementary transformations. The identity transformation can be defined as a static variable since all its coefficients are constant. For the other three transformations, we define functions that take the required parameters as arguments and construct the corresponding Affine objects: translation() returns a transformation that moves every point by an offset dx horizontally and dy vertically; scaling() returns a transformation that scales both coordinates by a common factor, and rotation() returns a transformation that rotates points by the given angle.

public static final Affine IDENTITY =
        new Affine(1, 0, 0, 1, 0, 0);

public static Affine translation(double dx, double dy) {
    return new Affine(1, 0, 0, 1, dx, dy);
}

public static Affine scaling(double factor) {
    return new Affine(factor, 0, 0, factor, 0, 0);
}

public static Affine rotation(double angle) {
    double cos = Math.cos(angle);
    double sin = Math.sin(angle);
    return new Affine(cos, -sin, sin, cos, 0, 0);
}

Combining Affine Transformations

Using these elementary transformations as building blocks, we can perform many interesting geometric transformations by applying multiple Affine objects after another. For example, suppose we want to compute the left branch of the Pythagoras tree using the BranchL transformation

\begin{equation*} \text {BranchL} = \text {Translate}(0,1)\cdot \text {Rotate}(\alpha )\cdot \text {Scale}(\cos \alpha ). \end{equation*}

This can be done by first computing the elementary transformations \(\text {Scale}(\cos \alpha )\), \(\text {Rotate}(\alpha )\), and \(\text {Translate}(0,1)\),

Affine translateL = Affine.translation(0, 1);
Affine rotateL = Affine.rotation(angle);
Affine scaleL = Affine.scaling(Math.cos(angle));

The corners of the transformed square are computed by applying these three transformations to the corners of the base square:

var baseShape = List.of(new Point(0, 0), new Point(1, 0),
        new Point(1, 1), new Point(0, 1));
var left = translateL.transformPoints(
        rotateL.transformPoints(scaleL.transformPoints(baseShape)));

To compute the next square along the left branch, we apply this sequence of transformations twice, for a total of six transformations. In general, the number of affine transformations we have to apply to compute a particular square in the Pythagoras tree increases with its distance from the root. Every time we move left in the tree, we have to perform the three transformations of BranchL, and every time we move right, we have to perform the four transformations of BranchR.

It is possible to speed up these computations significantly by making use of an important property of affine transformations: they are composable, which means that the effect of multiple affine transformations applied one after the other is again an affine transformation. This is obvious in simple cases: For example, rotating first by \(40^\circ \) and then once more by \(30^\circ \) is equivalent of rotating once by \(70^\circ \), and translating it first by a vector \(\vec {u}\) and then another vector \(\vec {v}\) is equivalent to translating once by \(\vec {u}+\vec {v}\).

In Exercise 3.3, we prove that this works for every pair of affine transformations: If \(A(\vec {p}) = \vec {A}\vec {p} + \vec {a}\) and \(B(\vec {p}) = \vec {B}\vec {p} + \vec {b}\), the function that corresponds to applying \(A\) and \(B\) one after another

\begin{equation*} C(\vec {p})=A(B(\vec {p})) \end{equation*}

is an affine transformation that has the following form:

\begin{equation} \label {eq:affine:compose} C(\vec {p}) = \vec {C}\vec {p} + \vec {c}, \qquad \text {where}\qquad \vec {C}=\vec {A}\vec {B}\quad \text {and}\quad \vec {c}=\vec {A}\vec {b} + \vec {a}. \end{equation}

In other words, the matrix and vector parts of \(C\) are obtained by combining the parts of \(A\) and \(B\).

We will now use these identities to combine multiple Affine objects. First, we determine the coefficients of \(\vec {C}\) and \(\vec {c}\) by writing the transformations \(A\) and \(B\) in terms of their coefficients and then evaluating the matrix products in Eq. (3.4). If we set

\begin{equation*} A(\vec {p}) = \begin{pmatrix} a_{00} & a_{01}\\ a_{10} & a_{11}\\ \end {pmatrix}\vec {p} + \begin{pmatrix} a_x\\ a_y \end {pmatrix}\quad \text {and}\quad B(\vec {p}) = \begin{pmatrix} b_{00} & b_{01}\\ b_{10} & b_{11}\\ \end {pmatrix}\vec {p} + \begin{pmatrix} b_x\\ b_y \end {pmatrix}, \end{equation*}

we obtain the following results for \(\vec {C}\) and \(\vec {c}\):

\begin{align} \label {eq:affine:matrix} \vec {C}&=\vec {A}\vec {B}= \begin{pmatrix} a_{00}b_{00} + a_{01}b_{10} & a_{00}b_{01} + a_{01}b_{11}\\ a_{10}b_{00} + a_{11}b_{10} & a_{10}b_{01} + a_{11}b_{11} \end {pmatrix},\\ \label {eq:affine:vector} \vec {c}&=\vec {A}\vec {b} + \vec {a} = \begin{pmatrix} a_{00} b_x + a_{01} b_y + a_x\\ a_{10} b_x + a_{11} b_y + a_y \end {pmatrix}. \end{align}

We can now define a method times() that multiplies this by another affine transformation t. The implementation shown in Listing 3.2 uses Eqs. (3.5) and (3.6) to compute the coefficients of the new transformation.

public Affine times(Affine t) {
    return new Affine(a * t.a + b * t.c,
            a * t.b + b * t.d,
            c * t.a + d * t.c,
            c * t.b + d * t.d,
            a * t.tx + b * t.ty + tx,
            c * t.tx + d * t.ty + ty);
}

Because times() returns a new instance of Affine, calls to times() can be chained to apply multiple affine transformations in sequence. For example, we can construct the BranchL transformation for the left arm of the Pythagoras tree by starting with \(\text {Translate}(0,1)\) and then multiplying it successively by \(\text {Rotate}(\alpha )\) and \(\text {Scale}(\cos \alpha )\):

Affine branchL = Affine.translation(0, 1)
    .times(Affine.rotation(alpha))
    .times(Affine.scaling(Math.cos(alpha)));

Since sequences of affine transformations are so common in practice, we also define a second method compose() that takes multiple Affine objects and collapses them into a single transformation (Listing 3.3). Similar to the way we just constructed branchL in the previous example, the function combines the transformations by accumulating their product using times(). Notice that this implementation of compose() also works correctly if the argument transforms is either empty or contains just a single element: Since result is initialized to the identity transformation, the composition of zero transformations returns IDENTITY, and the composition of one transformation returns that transformation itself.

public static Affine compose(Affine... transforms) {
    Affine result = IDENTITY;
    for (Affine t : transforms)
        result = result.times(t);
    return result;
}

Using compose() we can construct the transformation that computes the left branch using a notation that is even closer to the mathematical definition in Eq. (3.1):

Affine branchL = Affine.compose(
    Affine.translation(0, 1),
    Affine.rotation(angle),
    Affine.scaling(Math.cos(angle)));

Exercises

[3.3]Show that the combination of two affine transformations \(A(\vec {p}) = \vec {A}\vec {p} + \vec {a}\) and \(B(\vec {p}) = \vec {B}\vec {p} + \vec {b}\) is another affine transformation \(C\) and derive Eq. (3.4).

3.3 Constructing the Pythagoras Tree¶

We can now finally construct the Pythagoras tree itself. We start by defining a PythagorasTree class with three fields in Listing 3.4: UNIT_SQUARE is the unit square at the root of the tree, which we store as a list of its four corners; branchL is the affine transformation that transforms the unit square into the base square of the left branch of the tree; and branchR is the same for the right branch. The constructor takes the desired branching angle as its only argument and precomputes the two transformations.

// A class for computing Pythagoras trees.
public class PythagorasTree {
    private static final List<Point> UNIT_SQUARE = List.of(
            new Point(0, 0), new Point(1, 0),
            new Point(1, 1), new Point(0, 1));
    private final Affine branchR, branchL;

    public PythagorasTree(double angle) {
        branchL = Affine.compose(
                Affine.translation(0, 1),
                Affine.rotation(angle),
                Affine.scaling(Math.cos(angle)));
        branchR = Affine.compose(
                Affine.translation(1, 1),
                Affine.rotation(-Math.PI / 2 + angle),
                Affine.scaling(Math.sin(angle)),
                Affine.translation(-1, 0));
    }

    // ...
}

Our goal is to compute a list of all squares that make up the Pythagoras tree, from the base square to all the leaves and branches. The Pythagoras tree of depth 0 consists only of the base square. For larger depths, the tree can be computed recursively and consists of the following squares:

• • The base square.

• • The left arm, which we obtain by constructing a Pythagoras tree of depth \(n-1\) and transforming its squares using BranchL.

• • The right arm, which we obtain by transforming the depth-\(n-1\) tree using BranchR.

Listing 3.5 shows how to translate this definition into a recursive algorithm. The buildTreeSimple() method takes the desired depth of the tree as its only argument and returns a nested list of points in which each sub-list consists of the four corners of one square. After adding the unit square to this list, buildTreeSimple() calls itself recursively to construct the Pythagoras tree of order depth - 1. It then transforms the resulting squares using branchL and branchR to form the left and right branches of the tree.

List<List<Point>> buildTreeSimple(int depth) {
    var shapes = new ArrayList<List<Point>>();
    shapes.add(UNIT_SQUARE);
    if (depth > 0) {
        for (List<Point> shape : buildTreeSimple(depth - 1)) {
            shapes.add(branchL.transformPoints(shape));
            shapes.add(branchR.transformPoints(shape));
        }
    }
    return shapes;
}

Transforming Each Square Just Once

It’s instructive to study the problem from a slightly different angle that allows us to compute the squares in the Pythagoras tree more directly, without having to repeatedly transform entire sub-trees. To see how this might work, consider the leftmost leaf in the Pythagoras tree, the leaf you reach by starting at the root of the tree and repeatedly following the left branch. Each square along the path to this leaf is computed by transforming the previous square using BranchL, and the leaf is reached after \(n-1\) such transformations, if \(n\) is the order of the Pythagoras tree. In other words, the leaf is obtained by transforming the base square \(n-1\) times using \(\text {BranchL}\):

\begin{equation*} \text {leaf} = \text {BranchL}(\text {BranchL}(\cdots {} \text {BranchL}(\text {base}))); \end{equation*}

A similar argument shows that the rightmost leaf can be computed by applying \(\text {BranchR}\) \(n-1\) times, and in fact every square in the Pythagoras tree can be computed by a sequence of transformations that matches the path from the root to that square, applying \(\text {BranchL}\) each time we move left and \(\text {BranchR}\) each time we move right.

Instead of applying all these transformations one by one, we can again exploit the fact that a sequence of affine transformations can be combined into a single transformation. For instance, the corners of the leftmost leaf can also be computed by first composing \(n-1\) instances of \(\text {BranchL}\) into a single affine transformation, which is then applied to the corners of the base square:

\begin{equation*} \text {leaf} = (\text {BranchL}\cdot {}\text {BranchL}\cdot \cdots {}\cdot \text {BranchL})(\text {base}) \end{equation*}

Likewise, the affine transformations that correspond to other squares of the tree are obtained by composing different combinations of BranchL and BranchR transformations.

It’s easy to modify the algorithm for drawing Pythagoras trees to track the affine transformation of each square as it traverses the tree. The implementation in Listing 3.6 consists of two methods. Most of the work is done by buildSquares(), which recursively computes the squares a Pythagoras tree of the given depth and adds them to result. The first argument transform is the affine transformation that computes the current node’s square from UNIT_SQUARE, and the first action of buildSquares() is to compute this square and add it to result. The function then calls itself recursively to construct the left and right branches in the same way. Every time it descends into either the left or right branch, it combines the current transform with one additional instance of branchL or branchR, which ensures that the entire sub-tree is transformed appropriately.

private void buildSquares(Affine transform, int depth,
        List<List<Point>> result) {
    result.add(transform.transformPoints(UNIT_SQUARE));
    if (depth > 0) {
        buildSquares(branchL.times(transform), depth - 1, result);
        buildSquares(branchR.times(transform), depth - 1, result);
    }
}

public List<List<Point>> buildTree(int depth) {
    var shapes = new ArrayList<List<Point>>();
    buildSquares(Affine.IDENTITY, depth, shapes);
    return shapes;
}

The second method buildTree() in Listing 3.6 starts the construction process by calling buildSquares() with the identity transformation as the first argument, the desired total depth of the tree as the second, and an empty list of shapes as the last argument.

Exercises

[3.4]If you point a video camera at a monitor that displays a live feed of the camera, the result is a feedback loop in which the monitor shows a monitor that shows a monitor that… and so on. To construct a similar shape geometrically, start with a rectangle (or any other polygon) and compute a sequence of nested shapes, each of which touches the edges of the surrounding shape. Two examples of such whirl patterns are shown in the following image:

Describe iterative and recursive algorithms that construct such whirl patterns given the corners of the outer polygon.

[3.5]Experiment with the construction method for Pythagoras trees. For which branching angle do you obtain a symmetric fractal? What happens if you use as the base shape a polygon of your choice instead of the unit square?

3.4 Problems¶

Recursive Plants

[3.6]Figure 3.5 shows three recursive shapes that resemble plants. They are constructed by drawing a stem and then attaching two or more scaled and rotated copies of the whole shape. The shapes are characterized by the branching factor \(n\), which is the number of branches attached to the stem, as well as \(2n\) additional parameters that determine the relative size and orientation of each branch. Each left branch of the first shape, for instance, is scaled by a factor of 0.8 and rotated by 0.4 rad, and each right branch is scaled by a factor of 0.7 and rotated right by 0.25 rad. Write a program that computes or draws these kinds of plants. Hint: use polar coordinates or affine transformations to rotate and shorten branches.

Fibonacci Numbers and Trees

[3.7]The simplest examples of recursion come from mathematics and involve sequences of numbers. The Fibonacci sequence, for example, consists of the integers

\begin{equation*} 0, 1, 1, 2, 3, 5, 8, 13, \dots \end{equation*}

With the exception of the first two numbers 0 and 1, we can compute every number in the Fibonacci sequence by adding the two numbers that come before it. If we call the \(n\)th number in the sequence the Fibonacci number \(F_n\), we can write this as

\begin{equation} \label {eq:fibrec} F_n = F_{n-1}+F_{n-2},\quad \text {for $n\ge 2$.} \end{equation}

This is the recursive definition of the Fibonacci sequence. Since it is valid only for \(n\ge 2\), we have to define the first two entries of the sequence explicitly:

\begin{equation} \label {eq:fibbase} F_0 = 0,\quad F_1 = 1. \end{equation}

This is the base case of the definition.

• a) Implement two functions for computing the \(n\)th Fibonacci number, one that uses recursion and one that uses iteration.

The recursive definition tells us how to compute \(F_n\) under the assumption that we already know the values of \(F_{n-1}\) and \(F_{n-2}\). If we want to compute a particular value, we have to follow the chain of recursive steps back to the base cases. To compute \(F_5\), for example, the recursive definition first requires us to determine \(F_4\) and \(F_3\) which in turn requires us to determine \(F_3\), \(F_2\), and \(F_1\). Following the recursive definition two more times eventually reduces all computations to the two base cases \(F_1\) and \(F_0\). The resulting computation takes the form of the Fibonacci tree[Fibonacci trees] shown in Fig. 3.6 in which the inner nodes represent values defined recursively and the leaves represent the base cases.

• b) Following the illustration in Fig. 3.6, draw the Fibonacci trees of order 0 to order \(4\).

• c) Find the formula for the width and height of an order-\(k\) Fibonacci tree.

• d) Write a program that computes a Fibonacci tree of order \(k\). The program should output the coordinates of every node in the tree together with the Fibonacci number it contains. For instance, the output for the order-\(8\) tree might start with the following lines:

  1 at (0.0, 0.0)
  0 at (1.0, 0.0)
  1 at (0.5, 1.0)
  1 at (2.0, 1.0)
  2 at (1.0, 2.0)
  1 at (3.0, 1.0)
  ...
  

  Here, we place the bottom-left node at the origin; other conventions are equally valid.

The Towers of Hanoi

[3.8] In 1883 the French mathematician Édouard Lucas published a puzzle he called the Towers of Hanoi, based on a purported “old Indian legend” of a sacred tower that stands at the Temple of Benares. This tower consists of 64 golden disks that are all different in size and are stacked on top of each other on a long wooden peg, with the largest disk forming the base of the tower and the smallest disk at its top. Next to the tower are two identical pegs, and it’s possible to move the topmost disk from one peg to another. The only rule is that a large disk may never be placed on top of a smaller disk. Legend has it that, once the priests have transferred all 64 disks of the tower to another peg, the tower will collapse and the world will come to an end.

• a) Figure 3.7 shows a smaller four-disk version of the Towers of Hanoi. Describe the steps that are necessary to move the tower from peg A to peg B.

• b) Describe a general recursive algorithm for solving the Towers of Hanoi with \(n\) disks.

• c) Write a program that solves the Towers of Hanoi for a given number of disks \(n\), and arbitrary starting and destination pegs. For each move, your program should print the exact disk that is being transferred and the source and destination pegs.

• d) How many moves are necessary to transfer an \(n\)-disk tower? How many years will it take the priests to move all 64 disks of the original Tower of Hanoi?

Every legal configuration of disks can be obtained placing the disks one after the other, starting with the largest disk and ending with the smallest one. The sequence of the pegs on which the disks are placed uniquely identifies the configuration. For example, the following configuration of disks

is called “BCBAC”, since it is obtained by placing the largest disk is on B, the second-largest on C, and the three smallest disks on B, A, and C, in this order.

• e) Given three disks in the ABA configuration, what is the fastest way to transform them into the BAB configuration? What are the names of the intermediate configurations?

• f) Assume you want to find to find the shortest sequence of moves that transforms any valid arrangement of \(n\) disks into any other arrangement. Generalize the recursive algorithm for solving the Towers of Hanoi to find the optimal sequence of moves to transform configurations. Assume that the two configurations are given as a pair of strings. How many steps are necessary to transform BCBAC into CCCCC?

3.5 Chapter Notes¶

Iteration and recursion are equally powerful from a theoretical perspective: Every computation that can be performed using iteration can also be performed using recursion, and vice versa. At the hardware level, computers are inherently iterative and have no built-in notion of recursion. Most general-purpose programming languages, including Java, support both iteration in the form of loops and recursion in the form of recursive function calls.

Since computers only understand iteration, compilers simulate recursive functions by carefully storing and restoring the values of local variables before and after every function call. The data structure that holds these variables is known as the call stack. It is important to understand that this call stack has a limited size of only a few megabytes (the exact size depends on the programming language and operating system), which is more than enough for handling regular functions and simple forms of recursion. But deeply nested function calls can easily exceed the size of the call stack and cause the program to crash with a stack overflow error.

In several functional programming languages such as Erlang and Haskell, there are no explicit loops, and all forms of repetition must be expressed using recursive functions. Such languages implement a special optimization known as tail-call optimization that can often eliminate the overhead of recursion and prevent the call stack from overflowing. The main idea behind this optimization is the observation that a recursive function call that appears at the very end of a function (the “tail position”) can be replaced with a jump back to the beginning of the function. For example, in the following function, the recursive call to printIntegers() is in the tail position

void printIntegers(int i) {
    System.out.println(i);
    if (i >= 10)
        return;
    printIntegers(i + 1);
}

and can be transformed into a jump back to the start of the function:

void printIntegers(int i) {
start:
    System.out.println(i);
    if (i >= 10)
        return;
    i = i + 1;
    goto start;
}

With tail-call optimization, simple forms of recursion become as efficient as iteration. In case you were wondering, Java does not perform tail-call optimization, so loops remain the preferred way to perform iteration.

Affine transformations are widely used in computer graphics to move, scale, and rotate graphical objects in 2D and 3D. Our discussion of the Pythagoras tree demonstrated their main advantage: Affine transformations let us construct complex geometric objects out of smaller parts whose orientation, relative position, and size are specified using a single affine transformation. A generalization of this idea is the scene graph, in which everything that appears in a window or on the screen is modeled as a single tree or graph of transformed geometric objects. For more on these subjects, refer to one of the many books on computer graphics [69, 54, 85].

There are countless variations of the Towers of Hanoi problem we discussed in Exercise 3.8. In the Cyclic Towers of Hanoi, for instance, the three pegs are arranged in a circle and pegs can only be moved in the clockwise direction [7]. In the Bicolor Towers of Hanoi, we start with two towers whose disks have alternating colors, and the goal is to produce two towers of the same color. For a comprehensive account, see the book by Hinz el al. [51].