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
