Java Reference
In-Depth Information
23
for
(
int
counter =
0
; counter <=
40
; counter++)
24
System.out.printf(
"Fibonacci of %d is: %d%n"
, counter,
25
fibonacci(BigInteger.valueOf(counter))
);
26
}
27
}
// end class FibonacciCalculator
Fibonacci of 0 is: 0
Fibonacci of 1 is: 1
Fibonacci of 2 is: 1
Fibonacci of 3 is: 2
Fibonacci of 4 is: 3
Fibonacci of 5 is: 5
Fibonacci of 6 is: 8
Fibonacci of 7 is: 13
Fibonacci of 8 is: 21
Fibonacci of 9 is: 34
Fibonacci of 10 is: 55
...
Fibonacci of 37 is: 24157817
Fibonacci of 38 is: 39088169
Fibonacci of 39 is: 63245986
Fibonacci of 40 is: 102334155
Fig. 18.5
|
Recursive fibonacci method. (Part 2 of 2.)
The call to method
fibonacci
(line 25) from
main
is
not
a recursive call, but all sub-
sequent calls to
fibonacci
performed from lines 16-17 of Fig. 18.5 are recursive, because
at that point the calls are initiated by method
fibonacci
itself. Each time
fibonacci
is
called, it immediately tests for the
base cases
—
number
equal to 0 or
number
equal to 1 (lines
12-13). We use
BigInteger
constants
ZERO
and
ONE
to represent the values 0 and 1,
respectively. If the condition in lines 12-13 is
true
,
fibonacci
simply returns
number
,
because
fibonacci(0)
is 0 and
fibonacci(1)
is 1. Interestingly, if
number
is greater than
1, the recursion step generates
two
recursive calls (lines 16-17), each for a slightly smaller
problem than the original call to
fibonacci
. Lines 16-17 use
BigInteger
methods
add
and
subtract
to help implement the recursive step. We also use a constant of type
BigInteger
named
TWO
that we defined at line 7.
Analyzing the Calls to Method
Fibonacci
Figure 18.6 shows how method
fibonacci
evaluates
fibonacci(3)
. At the bottom of the
figure we're left with the values 1, 0 and 1—the results of evaluating the
base cases
. The
first two return values (from left to right), 1 and 0, are returned as the values for the calls
fibonacci(1)
and
fibonacci(0)
. The sum 1 plus 0 is returned as the value of
fibonac-
ci(2)
. This is added to the result (1) of the call to
fibonacci(1)
, producing the value 2.
This final value is then returned as the value of
fibonacci(3)
.
Figure 18.6 raises some interesting issues about
the order in which Java compilers eval-
uate the operands of operators
. This order is different from that in which operators are
applied to their operands—namely, the order dictated by the rules of operator precedence.
From Figure 18.6, it appears that while
fibonacci(3)
is being evaluated, two recursive
calls will be made—
fibonacci(2)
and
fibonacci(1)
. But in what order will they be
