The loop can be replaced by a recursive function f() that prints the current value of i and then calls itself as long as i < 10:
void f(int i) {
if (i >= 10)
return;
System.out.println(i):
f(i + 1);
}
To print the numbers between 0 and \(10\), you call f(0) with the starting value 0.
Solution to Exercise 3.2
Assume we are given a non-empty list \(X=x_0\ldots x_n\) and split it into a left part \(L=x_0\ldots x_{k-1}\) and a right part \(R=x_k\ldots x_n\); the position \(k\) at which we perform the split doesn’t matter. It’s now easy to see that the reverse of \(X\) is equal to the reverse
of \(R\) followed by the reverse of \(L\):
Listing C.11 shows an implementation of this technique.
Listing C.11ch3 / ReverseList
static List<Integer> reverse(List<Integer> list) {
if (list.size() <= 1)
return list;
var left = list.subList(0, list.size() / 2);
var right = list.subList(list.size() / 2, list.size());
var result = new ArrayList<>(reverse(right));
result.addAll(reverse(left));
return result;
}
Solution to Exercise 3.3
To derive the formula for \(C\), we simply plug the definition of \(B\) into \(A\) and reorder the resulting terms:
On the right-hand side, the matrix product \(\vec {A}\vec {B}\) produces a \(2\times 2\)-matrix and the expression \(\vec {A}\vec {b} + \vec {a}\) is a vector, so the result does in fact have the form of an affine transformation. If we set \(\vec {C}=\vec {A}\vec {B}\) and \(\vec {c}=\vec
{A}\vec {b} + \vec {a}\), we obtain Eq. (3.4).
Solution to Exercise 3.4
A recursive algorithm for computing whirl shapes is shown in Listing C.12. The arguments of whirl() are the corners of the base shape, a parameter fraction that determines where the corners of the nested shapes are placed
along the edges of shape, and depth, the number of nested shapes that should be computed. The resulting polygons are stored as a nested list of points in result. The helper method nested() computes the corners of the nested polygon by moving each
corner of shape toward the next corner. The iterative solution can be obtained by using a for loop to compute the list of nested shapes.
Listing C.12ch3 / Whirl
public void whirl(List<Point> shape, double fraction, int depth,
List<List<Point>> result) {
if (depth > 0) {
result.add(shape);
whirl(nested(shape, fraction), fraction, depth - 1, result);
}
}
static List<Point> nested(List<Point> shape, double fraction) {
int n = shape.size();
var nested = new ArrayList<Point>(n);
for (int i = 0; i < n; i++) {
nested.add(Point.lerp(shape.get(i), shape.get((i + 1) % n),
fraction));
}
return nested;
}
The drawPlant() function shown in Listing C.13 draws recursive plants similar to those shown in Fig. 3.5. The arrays factors[] and angles[]
hold the parameters of the plants and remain unchanged, and is g is the graphics context that is used for drawing the lines. The remaining parameters specify the geometry of the current branch: its starting point start, its length, and the current angle.
Each invocation of drawPlant() draws the current branch as a line from start to its endpoint, which is determined by the values of length and angle. Each sub-plant is then drawn by calling drawPlant() recursively, with the length
multiplied by factors[i] and the angle increased by angles[i].
Listing C.13ch3 / RecursivePlant
public static void drawPlant(double[] factors, double[] angles,
Point start, double length, double angle, int depth, Graphics g) {
if (depth <= 0)
return;
Point direction = Point.polar(length, angle);
Point end = new Point(start.x() + direction.x(),
start.y() + direction.y());
g.drawLine((int) start.x(), (int) start.y(),
(int) end.x(), (int) end.y());
for (int i = 0; i < factors.length; i++) {
drawPlant(factors, angles, end, length * factors[i],
angle + angles[i], depth - 1, g);
}
}
Solution to Exercise 3.7
a)Listing C.14 shows two implementations of the Fibonacci function. The recursive implementation fibRec() is a direct translation of the definitions (3.7) and (3.8). Since \(F_0=0\) and \(F_1=1\), the function simply returns the value of \(n\) itself if \(n\le 1\). For all other values of \(n\), fibRec() calls
itself recursively to compute \(F_{n-1}\) and \(F_{n-2}\) and then returns their sum. To compute the \(n\)th Fibonacci number iteratively, we start with the pair of numbers \((0,1)\) and repeatedly apply the mapping \((a,b)\mapsto (b,a+b)\):
The \(n\)th Fibonacci number is the first number of the \(n\)th pair in this sequence.
Listing C.14ch3 / Fibonacci
public static int fibRec(int k) {
if (k <= 1)
return k;
return fibRec(k - 1) + fibRec(k - 2);
}
public static int fib(int n) {
int a = 0, b = 1;
for (int i = 0; i < n; i++) {
int next = a + b;
a = b;
b = next;
}
return a;
}
b)The first few Fibonacci trees are shown in Fig. C.5. The first two Fibonacci trees consists of a single node. The others are obtained by attaching the previous two trees to a new root node.
Figure C.5 The first five Fibonacci trees.
c)As you can see in Fig. 3.6, the width of a Fibonacci tree of order \(k\) is proportional to the number of leaves in the tree. Let’s call the number of leaves of an order-\(k\) tree \(L_k\). The first two Fibonacci trees consist of
just a single node, so we have
\(\seteqnumber{0}{C.}{0}\)
\begin{equation}
L_0 = L_1 = 1
\end{equation}
In all other cases, \(L_k\) is the number of leaves in the left subtree plus the number of leaves in the right subtree. Since the left subtree is a Fibonacci tree of order \(n-1\) and the right subtree a Fibonacci tree of order \(n-2\), we have
The recursive definition of \(L_k\) is therefore almost identical to the definition of the Fibonacci numbers themselves and only differ for \(k=0\). It’s not hard to see that
\(\seteqnumber{0}{C.}{2}\)
\begin{equation}
L_k = F_{k+1}.
\end{equation}
For example, the number of leaves in Fig. 3.6 is \(F_9=21+13=34\). The height of a Fibonacci tree of order \(k\) is usually simply \(k\), except for \(k=0\) where the height is 1.
d)A program for constructing the Fibonacci tree of a given order is shown in Listing C.15. The parameter bottomLeft is the coordinate of the bottom-left corner of the entire tree. If the order is
0 or 1, we place a single leaf node at bottomLeft. Otherwise, we first compute the left and rigth subtrees and then the position of the root node. The lower-left corner of the left subtree is bottomLeft and the right subtree is moved right and up to
align the two subtrees at the top. The root node is placed centered above the two subtrees. The functions width() and height() compute the width and height of a Fibonacci tree using the formulas we derived in the part (c).
a)The key insight is that the largest disk can only be moved from A to B if the three small disks are on the rightmost peg. The four-disk problem can therefore be solved by first moving the three smallest disks from A to C, then the largest disk from A to B,
and finishing by moving three disks from C to B. To transfer the smaller three-disk tower we use the same strategy recursively.
b)Suppose we want to move a tower of \(n\) disks from the peg labeled X to another peg labeled Y. The third peg labeled Z is assumed to be empty or contain only larger disks. A recursive algorithm can then be formulated as follows:
c)The recursive implementation in Listing C.16 takes four arguments: the total number of disks numDisks, the number of disks n that should be moved, and the
source and destination pegs. We refer to the three pegs using the upper-case letters 'A', 'B', and 'C'. The function returns immediately if the tower is empty or source is
equal to destination. Otherwise, the index of the third peg tmp is computed using the following trick:
'A' + 'B' + 'C' - destination - source
This expression uses the fact that the numerical sum of all three peg indexes is always 'A'+'B'+'C'. The index of the largest disk being transferred in each step is numDisks + 1 - n.
Listing C.16ch3 / Hanoi
public static void solveHanoiMoves(
int numDisks, int n, char source, char destination) {
if (n == 0 || source == destination)
return;
int tmp = 'A' + 'B' + 'C' - destination - source;
solveHanoiMoves(numDisks, n - 1, source, (char) tmp);
System.out.printf("Move disk %d from %c to %c%n",
numDisks + 1 - n, source, destination);
solveHanoiMoves(numDisks, n - 1, (char) tmp, destination);
}
d)Transferring a three-disk tower requires 3 moves, and for a four-disk tower it’s already \(2\cdot 7+1=15\) moves. It’s easy to prove using induction that \(2^n-1\) moves are necessary to move an \(n\)-disk tower. Moving a 64-disk tower therefore requires
\(2^{64}-1\) or 18 446 744 073 709 551 615 moves. Even if the priests were able to move one disk per second, transferring the whole tower would take 585 billion years — 42 times the age of the known universe! It’s therefore quite likely that, almost no matter for how many centuries or millennia the priests have already been at work, the world will come to an end long before they are able to move the final disk.
e)The optimal way to reorganize the disks consists of five steps:
B to C, A to C, A to B, C to B, C to A.
The intermediate configurations are ABA, ACA, ACC, BCC, BCB, and BAB.
f)The problem can again be solved recursively. To transform the configuration \(x_0x_1\dots {}x_{n-1}\) into the configuration \(y_0y_1\dots {}y_{n-1}\), first move the \(n-1\) smallest disks out of the way, then move the largest disk from position \(x_0\) to position \(y_0\),
and finally move the \(n-1\) smallest disks to their correct positions. More specifically, if \(z\) is the third peg that differs from both \(x_0\) and peg \(y_0\), the steps are as follows:
1. Recursively move \(n-1\) disks from \(x_1 x_2\dots {}x_{n-1}\) to \(zz\dots {}z\).
2. Move a single disk from \(x_0\) to \(y_0\).
3. Recursively move \(n-1\) disks from \(zz\dots {}z\) to \(y_1y_2\dots {}y_{n-1}\).
As a special case, if \(x_0=y_0\), we only have to recursively transform \(x_1\dots {}x_{n-1}\) into \(y_1\dots {}y_{n-1}\). An implementation of this algorithm is shown in Listing C.17. It takes 26 steps to transform BCBAC into CCCCC.
Listing C.17ch3 / Hanoi
// Find a sequence of moves that solves the Towers of Hanoi for
// arbitrary start and end states.
public static void solveHanoiPath(String start, String end) {
int n = start.length();
if (n == 0)
return;
char x0 = start.charAt(0), y0 = end.charAt(0);
if (x0 == y0) {
solveHanoiPath(start.substring(1), end.substring(1));
} else {
char z = (char) ('A' + 'B' + 'C' - x0 - y0);
char[] tmp = new char[n - 1];
for (int i = 0; i < n - 1; i++)
tmp[i] = z;
solveHanoiPath(start.substring(1), new String(tmp));
System.out.println("Move disk from " + x0 + " to " + y0);
solveHanoiPath(new String(tmp), end.substring(1));
}
}
