Fibonacci.java

Download Fibonacci.java

 1: // Calculate the n-th Fibonacci number, using a recursive
 2: // method.  (This value can be calculated using a non-recursive
 3: // algorithm more more efficiently, but I want to demonstrate
 4: // recursion with a simple example.)
 5: // Note Java long will overflow after 92nd Fibonacci number,
 6: // but the inefficiency means it will take hours/days to compute
 7: // (roughly) the 60th Fibonacci number!  For a faster recursive algorithm,
 8: // see FibonacciMemo.java.  The fastest way is to avoid recursion; see
 9: // the iterative algorithm below.  To avoid the overflow, use BigInteger
10: // objects instead of a long.
11: //
12: // Usage: Pass in the number as a command line argument.
13: //
14: // Written 11/2016 by Wayne Pollock, Tampa Florida USA
15: 
16: class Fibonacci
17: {
18:    private static long count = 0; // count of the calls to the method fib
19: 
20:    public static void main ( String [] args )
21:    {
22:       int num = 0;
23:       try {
24:          num = Integer.parseInt( args[0] );
25:          if ( num < 0 )
26:             throw new IllegalArgumentException( "Must be a positive Integer" );
27:       } catch ( Exception e ) {
28:          System.err.println( "Usage: java Fibonacci <num>\n"
29:             + "\twhere <num> is a positive Integer" );
30:          System.exit( 1 );
31:       }
32: 
33:       System.out.println( "fib(" + num + ") = "
34:          + fib( num ) );
35:       System.out.println( "\nNumber of calls to method fib: " + count );
36:    }
37: 
38:    private static long fib ( int num )
39:    {
40:       ++count;  // Count how many times this method is invoked
41: 
42:       // fib(0) and fib(1) are 0 and 1 by definition:
43:       if ( num == 0 ) return 0;
44:       if ( num == 1 ) return 1;
45: 
46:       // fib(n) is fib(n-1) + fib(n-2) by definition:
47:       return fib( num-1 ) + fib( num-2 );
48:    }
49: }
50: 
51: /* Iterative version:
52: 
53:    public static void main ( String [] args )
54:    {
55:      // Test values:  Note the overflow that occurs for large values.
56:      int[] values = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 50, 92, 93, -1};
57: 
58:      for ( int val : values )
59:         System.out.println( "fib(" + val + ") = " + fib(val) );
60:    }
61: 
62:    private static long fib ( int num )
63:    {
64:       if ( num < 0 )
65:         throw new IllegalArgumentException("num must be non-negative!");
66: 
67:       if ( num == 0 ) return 0;
68:       if ( num == 1 ) return 1;
69: 
70:       // Initialize first two values:
71:       long previous = 0, current = 1, next;
72:       // Calculate fib(num):
73:       for ( int i = 2; i <= num; ++i ) {
74:          next = previous + current;
75:          previous = current;
76:          current = next;
77:       }
78:       return current;
79:    }
80: */