Java Reference
In-Depth Information
21 /**
22
Computes a Fibonacci number.
23 @param n
an integer
24 @return
the nth Fibonacci number
25 */
26
public static long
fib(
int
n)
27 {
28
if
(n <=
2
) return
1
;
29
long
fold =
1
;
30
long
fold2 =
1
;
31
long
fnew =
1
;
32
for
(
int
i =
3
; i <= n; i++)
33 {
34 fnew = fold + fold2;
35 fold2 = fold;
36 fold = fnew;
37 }
38
return
fnew;
39 }
40 }
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
606
607
This method runs much faster than the recursive version.
In this example of the
fib
method, the recursive solution was easy to program
because it exactly followed the mathematical definition, but it ran far more slowly
than the iterative solution, because it computed many intermediate results multiple
times.
