Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 149

When called with the statement

hanoi(3, 'A', 'B', 'C'); //transfer 3 disks from A to B using C

the function prints this:

Move disk from A to B
Move disk from A to C
Move disk from B to C
Move disk from A to B
Move disk from C to A
Move disk from C to B
Move disk from A to B

How many moves are required to transfer n disks?

• If n is 1, one move is required: (1 = 2

1 - 1).

• If n is 2, three moves are required: (3 = 2

2 - 1).

• If n is 3, seven moves (see as shown earlier) are required: (7 = 2

3 - 1).

It appears that, for n disks, the number of moves is 2 n - 1. It can be proved that this is indeed the case.
When n is 64, the number of moves is

2 64 - 1 = 18,446,744,073,709,551,615

Assuming the priests can move one disc per second, never make a mistake, and never take a rest, it will take them
almost 600 billion years to complete the task. Rest assured that the world is not about to end any time soon!

5.6 Writing Power Functions
Given a number, x , and an integer, n ³ 0, how do we calculate x raised to the power n , that is, x n ? We can use the
definition that x n is x multiplied by itself n-1 times. Thus, 3 4 is 3 × 3 × 3 × 3. Here is a function that uses this method:

public static double power(double x, int n) {
double pow = 1.0;
for (int h = 1; h <= n; h++) pow = pow * x;
return pow;
}

Note that if n is 0 , power returns 1 , the correct answer.
As written, this function performs n multiplications. However, we can write a faster function if we adopt a
different approach. Suppose we want to calculate x 16 . We can do it as follows:

• If we know

x8 = x 8 , we can multiply x8 by x8 to get x16 , using just one more multiplication.

• If we know

x4 = x 4 , we can multiply x4 by x4 to get x8 , using just one more multiplication.

x2 = x 2 , we can multiply x2 by x2 to get x4 , using just one more multiplication.
We know x ; therefore, we can find x2 using one multiplication. Knowing x2 , we can find x4 using one more
multiplication. Knowing x4 , we can find x8 using one more multiplication. Knowing x8 , we can find x 16 using one
more multiplication. In all, we can find x 16 using just four multiplications.

• If we know