Java Reference
In-Depth Information
The series: 0 1 1 2 3 5 8 13 21 34 55 89 . . .
indices: 0 1 2 3 4 5 6 7 8 9 10 11
The Fibonacci series begins with
0
and
1
, and each subsequent number is the sum of the pre-
ceding two. The series can be recursively defined as:
fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index - 2) + fib(index - 1); index >= 2
The Fibonacci series was named for Leonardo Fibonacci, a medieval mathematician, who
originated it to model the growth of the rabbit population. It can be applied in numeric opti-
mization and in various other areas.
How do you find
fib(index)
for a given
index
? It is easy to find
fib(2)
, because you
know
fib(0)
and
fib(1)
. Assuming that you know
fib(index - 2)
and
fib(index - 1)
,
you can obtain
fib(index)
immediately. Thus, the problem of computing
fib(index)
is
reduced to computing
fib(index - 2)
and
fib(index - 1)
. When doing so, you apply the
idea recursively until
index
is reduced to
0
or
1
.
The base case is
index = 0
or
index = 1
. If you call the method with
index = 0
or
index = 1
, it immediately returns the result. If you call the method with
index >= 2
, it divides
the problem into two subproblems for computing
fib(index - 1)
and
fib(index - 2)
using recursive calls. The recursive algorithm for computing
fib(index)
can be simply
described as follows:
if
(index ==
0
)
return
0
;
else if
(index ==
1
)
return
1
;
else
return
fib(index -
1
) + fib(index -
2
);
Listing 20.2 gives a complete program that prompts the user to enter an index and computes
the Fibonacci number for that index.
L
ISTING
20.2
ComputeFibonacci.java
1
import
java.util.Scanner;
2
3
public class
ComputeFibonacci {
4
/** Main method */
5
public static void
main(String[] args) {
6
// Create a Scanner
7 Scanner input =
new
Scanner(System.in);
8 System.out.print(
"Enter an index for a Fibonacci number: "
);
9
int
index = input.nextInt();
10
11
// Find and display the Fibonacci number
12 System.out.println(
"The Fibonacci number at index "
13 + index +
" is "
+
fib(index)
);
14 }
15
16
/** The method for finding the Fibonacci number */
17
public static long
fib(
long
index)
{
18
if
(index ==
0
)
// Base case
base case
19
return
0
;