Fibonacci numbers are also know as Fibonacci sequence or Fibonacci series.
The Fibonacci sequence is represented by a sequence of numbers, starting with 0 and 1, in which the next element is the sum of the preceding two elements. For instance, the following sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
represent a sequence of 13 Fibonacci numbers.
One common problem in computer programming is to print the first n elements in Fibonacci sequence. The solution can be implemented using an iterative algorithm or an recursive one. The recursive implementation of this problem in Java is as follow:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package org.code.programmers; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class FibonacciNumbers { public static void main(String args[]) throws NumberFormatException, IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Please enter the value for n: "); long n = new Long(reader.readLine()); for (int i = 1; i <= n; i++) { System.out.println(i + ": " + calculateFibonacciNumbers(i)); } } private static long calculateFibonacciNumbers(long number) { if (number <= 1) { return number; } else { return calculateFibonacciNumbers(number - 1) + calculateFibonacciNumbers(number - 2); } } } |
Of course, the above example is an inefficient one, as it is very slow (set a value greater than 50 and you will notice). Also the 93rd Fibonacci number will overflow a long.
The iterative implementation of the same problem could be as follow:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package org.code.programmers; import java.util.Scanner; /** * This program will print the first n element of the Fibonacci numbers */ public class IterativeFibonacciNumbers { public static void main(String args[]) { Scanner s = new Scanner(System.in); System.out.print("Please enter the value for n: "); calculateFibonacciNumbers(s.nextLong()); s.close(); } public static void calculateFibonacciNumbers(long n) { if (n == 0) { System.out.println("0"); } else if (n == 1) { System.out.println("0 1"); } else { System.out.println("0"); System.out.println("1"); long a = 0; long b = 1; for (int i = 1; i < n - 1; i++) { long nextNumber = a + b; System.out.println(nextNumber + " "); a = b; b = nextNumber; } } } } |
Note that the same remark as for the recursive implementation remain valid: the 93rd Fibonacci number will overflow the long. Instead, you will notice that the implementation is faster.