Java Reference

In-Depth Information

f(1)

f(2)

f(3)

f(4)

f(5)

FIGURE 14.2:
Example of computing the 5th Fibonacci number using dynamic program-

ming.

When executed, the program returns 44,945,570,212,850. If there are an average of one

million grains of wheat in a bushel and a bushel of wheat costs US

300, then the king

$

needs to give to the peasant grain that is worth a total of roughly US

13.5 billion. The king

decided that this was a small price to risk for the fairest maiden of them all. The peasant

liked that the king was prudent enough to do all the calculations and he let him win. The

king married the peasant's daughter and they lived happily ever after.

Let us examine in greater detail why the second solution to the problem is better. Since

the computations are performed bottom up, every Fibonacci number is calculated exactly

once; see Figure 14.2. The approach in which we start by calculating the answers to the

simplest problem and then we calculate the answers to more complicated problems as a

function of existing results is called
dynamic programming
.

$

In most cases, a dynamic programming solution is faster than a recursive solution.

Whenever possible, we should avoid using a recursive solution. However, in many

cases a dynamic programming solution is not obvious and even nonexistent, while a

recursive solution is straightforward to find and implement.

Next, let us examine a problem that is naturally suited for recursion. While a non-

recursive solution is certainly possible, it cannot be easily programmed. Consider the Tower

of Hanoi problem; see Figure 14.3. In the picture, there are 8 rings on the first needle. The

problem is to move them to the third needle. Only one ring can be moved at a time and a

ring can be placed only on top of a bigger ring.

Moving all eight rings in the right order seems a challenging task. However, if by magic,

someone can show us how to move seven rings, then the problem becomes significantly

easier. We just need to move seven rings from the first to the middle needle, the last ring

from the first to the last needle, and then the seven rings from the second to the last needle.

In this case, a recursive solution just comes naturally. On the other hand, it is not obvious