Exercise 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.
Figure 3.5 Plant-like shapes modeled using recursion.
Fibonacci Numbers and Trees
Exercise 3.7.The simplest examples of recursion come from mathematics and involve sequences of numbers. The
Fibonacci sequence, for example, consists of the integers
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
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:
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.
Figure 3.6 Fibonacci trees are defined recursively. Each node corresponds to a Fibonacci number \(F_n\) and its left and right children to the Fibonacci trees for \(F_{n-1}\) and \(F_{n-2}\) respectively.
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
Exercise 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 is 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.
Figure 3.7 The Towers of Hanoi. The goal is to move the entire stack of disks to another peg without placing a large disk on a smaller disks.
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?