In this article, we are going to explain the Fibonacci sequence in Java. We will see the Fibonacci series of numbers and how they can be generated in Java in various ways, like recursion and using the classical loop.
Fibonacci series generation is a classic interview question for entry-level programmers.
1. What is the Fibonacci series?
The Fibonacci series is a series of numbers in which the next number is found by adding two previous numbers. For example, Fibonacci series looks as below,
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on
- The first number is 0 and the second number is 1
- The third number 1 is found by adding previous 2 numbers 0 and 1
- The fourth number 2 is found by adding previous 2 numbers 1 and 1
- The fifth number 3 is found by adding previous 2 numbers 1 and 2
- The sixth number 5 is found by adding previous 2 numbers 2 and 3
- And the list continues with the same pattern
This pattern can be broken down to a formula,
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
| x(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … |
Let us assume 4th term can be represented as x(4) and the fifth term can be represented as x(5). In general, each term can be represented as x(n).
As per the pattern 6th term can be written as x(6) = x(4) + x(5). So formula can be written as,
x(n) = x(n-2) + x(n-1)
Here x(n) is the nth term, x(n-1) is teh previous term and x(n-2) is the term previous to that.
2. Fibonacci in Java with recursion
In this section, we are going to see how can we generate the Fibonacci series using recursion. Here we use the divide and conquer approach. In the divide and conquer technique the problem is broken down to two or more problems of the same or related type until it becomes simple enough to solve.
FibonacciGeneratorWithRecusion
import java.util.Scanner;
/**
* @author Santosh Balgar Sachchidananda
* FibonacciGeneratorWithRecusion generats Fibonacci series using recursion
*/
public class FibonacciGeneratorWithRecusion {
private int generateFibonacciNumber(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
return generateFibonacciNumber(n - 1) + generateFibonacciNumber(n - 2);
}
public static void main(String[] args) {
FibonacciGeneratorWithRecusion fg = new FibonacciGeneratorWithRecusion();
System.out.println("************** Generating Fibonacci Series using recursion *****************");
System.out.println("Enter number upto which Fibonacci series to print: ");
int number = new Scanner(System.in).nextInt();
for (int i = 0; i <= number; i++) {
System.out.print(fg.generateFibonacciNumber(i) + " ");
}
}
}
Let us analyze the time complexity of this algorithm. To calculate nth term we need to calculate (n-1)th and (n-2)th term plus adding them together to generate the final answer.
O(n) = O(n-1) + O(n-2) + O(1)
Recursive way to generate the Fibonacci number is costly.
3. Fibonacci in Java with for loop
In this section, we will see how can we generate the Fibonacci series using a simple for loop approach.
FibonacciGeneratorWithLoop
import java.util.Scanner;
public class FibonacciGeneratorWithLoop {
public static void main(String[] args) {
int previousNum = 1;
int secondPreviousNum = 0;
System.out.println("************** Generating Fibonacci Series with loop *****************");
System.out.println("Enter number upto which Fibonacci series to print: ");
int number = new Scanner(System.in).nextInt();
for (int i = 1; i <= number; i++) {
if (i == 1) {
System.out.print("0 ");
} else if (i == 2 || i == 3) {
secondPreviousNum = 1;
previousNum = 1;
System.out.print(" 1");
} else {
int fibonacciNum = previousNum + secondPreviousNum;
System.out.print(fibonacciNum + " ");
secondPreviousNum = previousNum;
previousNum = fibonacciNum;
}
}
}
}
Let us analyze the time complexity of this approach.
This approach is linear and we have to iterate through n time. Hence, the time complexity of the loop-based approach is O(n). This is more efficient as compared to the recursive approach.
4. Download the source code
In this article, we explained the Fibonacci sequence in Java through examples.
You can download the full source code of this example here: Fibonacci Java Example
