Java Reference
In-Depth Information
Entering fib: n = 4
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Exiting fib: n = 4 return value = 3
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Exiting fib: n = 5 return value = 5
Entering fib: n = 4
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Exiting fib: n = 4 return value = 3
Exiting fib: n = 6 return value = 8
fib(6) = 8
604
605
Figure 2
shows the call tree for computing
fib(6)
. Now it is becoming apparent
why the method takes so long. It is computing the same values over and over. For
example, the computation of
fib(6)
calls
fib(4)
twice and
fib(3)
three times.
That is very different from the computation we would do with pencil and paper. There
we would just write down the values as they were computed and add up the last two
to get the next one until we reached the desired entry; no sequence value would ever
be computed twice.
If we imitate the pencil-and-paper process, then we get the following program.
