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.