Recursion - Data Structures and Abstractions with Java - page 176

After moving the largest disk (Figure 7-9c), the optimal algorithm moves n - 1 disks from
pole 2 to pole 3 in another M ( n - 1) = m ( n - 1) moves. Altogether, the optimal algorithm makes at
least 2 M ( n - 1) + 1 moves. Thus,

M ( n ) ≥ 2 M ( n - 1) + 1

Now apply the assumption that M ( n - 1) = m ( n - 1) and then the recurrence for m ( n ) given in
Segment 7.32 to get

M ( n ) ≥ 2 m ( n - 1) + 1 = m ( n )

m ( n ). But since the optimal algorithm cannot require
more moves than our algorithm, the expression M ( n ) > m ( n ) cannot be true. Thus, we must
have M ( n ) = m ( n ) for all n

We have just shown that M ( n ) ≥

≥ 1.

7.36

Finding an iterative algorithm to solve the Towers of Hanoi problem is not as easy as finding a recur-
sive algorithm. We now know that any iterative algorithm will require at least as many moves as the
recursive algorithm. An iterative algorithm will save the overhead—space and time—of tracking the
recursive calls, but it will not really be more efficient than solveTowers . An algorithm that uses both iter-
ation and recursion to solve the Towers of Hanoi problem is discussed in the section “Tail Recursion,” and
an entirely iterative algorithm is the subject of Project 7 at the end of this chapter.

A Poor Solution to a Simple Problem

Some recursive solutions are so inefficient that you should avoid them. The problem that we will
look at now is simple, occurs frequently in mathematical computations, and has a recursive solution
that is so natural that you are likely to be tempted to use it. Don't!

7.37

Example: Fibonacci numbers. Early in the 13th century, the mathematician Leonardo Fibonacci
proposed a sequence of integers to model the number of descendants of a pair of rabbits. Later
named the Fibonacci sequence , these numbers occur in surprisingly many applications.
The first two terms in the Fibonacci sequence are 1 and 1. Each subsequent term is the sum of
the preceding two terms. Thus, the sequence begins as 1, 1, 2, 3, 5, 8, 13, . . . Typically, the
sequence is defined by the equations

F 0 = 1
F 1 = 1
F n = F n -1 + F n -2 when n

≥ 2

You can see why the following recursive algorithm would be a tempting way to generate the sequence:

Algorithm Fibonacci(n)
if (n <= 1)
return 1
else
return Fibonacci(n - 1) + Fibonacci(n - 2)

7.38

This algorithm makes two recursive calls. That fact in itself is not the difficulty. Earlier, you saw
perfectly good algorithms— displayArray in Segment 7.18 and solveTowers in Segment 7.31—
that make several recursive calls. The trouble here is that the same recursive calls are made
repeatedly. A call to Fibonacci(n) invokes Fibonacci(n - 1) and then Fibonacci(n - 2) . But
the call to Fibonacci(n - 1) has to compute Fibonacci(n - 2) , so the same Fibonacci number is
computed twice.