Java Reference
In-Depth Information
f
1
= 1
f
2
= 1
f
n
=
f
n ɨ 1
+
f
n ɨ 2
That is, each value of the sequence is the sum of the two preceding values. The first
ten terms of the sequence are
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
It is easy to extend this sequence indefinitely. Just keep appending the sum of the last
two values of the sequence. For example, the next entry is 34+55=89.
We would like to write a function that computes f
n
for any value of n. Let us translate
the definition directly into a recursive method:
ch13/fib/RecursiveFib.java
1
import
java.util.Scanner;
2
3 /**
4
This program computes Fibonacci numbers using a recursive
5
method.
6 */
7
public class
RecursiveFib
8 {
9
public static void
main(String[] args)
10 {
11 Scanner in =
new
Scanner(System.in);
12 System.out.print(
"Enter n: "
);
13
int
n = in.nextInt();
14
15 for (int i =
1
; i <= n; i++)
16 {
17
long
f = fib(i);
18 System.out.println(
"fib("
+ i +
") = "
+ f);
19 }
20 }
602
603
