Java Program - Fibonacci Sequence
Fibonacci terms are generally represented as Fn. A Fibonacci term is the sum of two previous terms and starts with 0 and 1. Mathematically, it can be represented as:
Fn = Fn-1 + Fn-2
With boundary conditions: F0 = 0 and F1 = 1
The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...
Method 1: Using Recursive method
In the example below, a recursive method called fib() is created to find out the nth term of Fibonacci sequence.
public class MyClass { static int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n-1) + fib(n-2); } public static void main(String[] args) { System.out.println("Fibonacci 5th term: " + fib(5)); System.out.println("Fibonacci 6th term: " + fib(6)); System.out.println("Fibonacci 7th term: " + fib(7)); } }
The above code will give the following output:
Fibonacci 5th term: 5 Fibonacci 6th term: 8 Fibonacci 7th term: 13
Method 2: Using Dynamic Programming
The Fibonacci term can also be estimated using dynamic programming. As compared to the recursive method, it calculates a specific term of the sequence only once.
public class MyClass { static int fib(int n) { //creating array which contains Fibonacci terms int[] f = new int[n+1]; f[0] = 0; f[1] = 1; for(int i = 2; i <= n ; i++) { f[i] = f[i-1] + f[i-2]; } return f[n]; } public static void main(String[] args) { System.out.println("Fibonacci 6th term: " + fib(6)); System.out.println("Fibonacci 7th term: " + fib(7)); System.out.println("Fibonacci 8th term: " + fib(8)); } }
The above code will give the following output:
Fibonacci 6th term: 8 Fibonacci 7th term: 13 Fibonacci 8th term: 21
Method 3: Using Ternary Operator
This can also be achieved using ternary operator.
public class MyClass { static int fib(int n) { int y = (n == 0)? 0 : (n == 1) ? 1 : fib(n-1) + fib(n-2); return y; } public static void main(String[] args) { System.out.println("Fibonacci 8th term: " + fib(8)); System.out.println("Fibonacci 9th term: " + fib(9)); System.out.println("Fibonacci 10th term: " + fib(10)); } }
The above code will give the following output:
Fibonacci 8th term: 21 Fibonacci 9th term: 34 Fibonacci 10th term: 55
Method 4: Space optimized method
In this method, only three variables are used which changes in each iteration and finally nth term of Fibonacci Sequence is calculated.
public class MyClass { static int fib(int n) { int a = 0, b = 1, c = 0; if (n == 0) return a; for(int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } public static void main(String[] args) { System.out.println("Fibonacci 9th term: " + fib(9)); System.out.println("Fibonacci 10th term: " + fib(10)); System.out.println("Fibonacci 11th term: " + fib(11)); } }
The above code will give the following output:
Fibonacci 9th term: 34 Fibonacci 10th term: 55 Fibonacci 11th term: 89
Method 5: Using power of matrix
A Fibonacci sequence term can also be calculated as power of matrix. A Fibonacci sequence holds below mentioned property:
To calculate Fn,is calculated and A01 will be the Fn.
public class MyClass { static int fib(int n) { int[][] initial = {{1,1},{1,0}}; int[][] Final = {{1,1},{1,0}}; int a, b, c, d; if (n == 0) return 0; else { for(int i = 1; i < n ; i++){ a = Final[0][0]*initial[0][0] + Final[0][1]*initial[1][0]; b = Final[1][0]*initial[0][0] + Final[1][1]*initial[1][0]; c = Final[0][0]*initial[0][1] + Final[0][1]*initial[1][1]; d = Final[1][0]*initial[0][1] + Final[1][1]*initial[1][1]; Final[0][0] = a; Final[1][0] = b; Final[0][1] = c; Final[1][1] = d; } } return Final[0][1]; } public static void main(String[] args) { System.out.println("Fibonacci 10th term: " + fib(10)); System.out.println("Fibonacci 11th term: " + fib(11)); System.out.println("Fibonacci 12th term: " + fib(12)); } }
The above code will give the following output:
Fibonacci 10th term: 55 Fibonacci 11th term: 89 Fibonacci 12th term: 144
Recommended Pages
- Java Program - To Check Prime Number
- Java Program - Bubble Sort
- Java Program - Selection Sort
- Java Program - Maximum Subarray Sum
- Java Program - Reverse digits of a given Integer
- Java Program - Merge Sort
- Java Program - Shell Sort
- Stack in Java
- Queue in Java
- Java Program - Find LCM of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable
- Java Program - To Check Armstrong Number
- Java Program - Counting Sort
- Java Program - Radix Sort
- Java Program - Find Largest Number among Three Numbers
- Java Program - Print Floyd's Triangle