Java Reference
In-Depth Information
21
22 /**
23
Computes a Fibonacci number.
24 @param n
an integer
25 @return
the nth Fibonacci number
26 */
27
public static long
fib(
int
n)
28 {
29
if
(n <=
2
)
return
1
;
30
else return
fib(n -
1
) + fib(n -
2
);
31 }
32 }
Output
Enter n:
50
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
È
fib(50) = 12586269025
That is certainly simple, and the method will work correctly. But watch the output
closely as you run the test program. The first few calls to the
fib
method are quite
fast. For larger values, though, the program pauses an amazingly long time between
outputs.
That makes no sense. Armed with pencil, paper, and a pocket calculator you could
calculate these numbers pretty quickly, so it shouldn't take the computer anywhere
near that long.
To find out the problem, let us insert trace messages into the method:
603
604
ch13/fib/RecursiveFibTracer.java
1
import
java.util.Scanner;
2
