Fibonacci Series in Java: Different Ways Explained With Examples
Basics of Python
5 Hrs. duration
9 Modules
1800+ Learners
Start Learning
The Fibonacci series is a famous sequence in mathematics and computer Science. In this
series, two consecutive numbers are added together. This makes the next number. It starts with 0 and 1. So the
sequence looks like this:
0 1, 1 2, 3 5, 8 13, 21 34.
Why does this sequence matter so much? Many numbers in the Fibonacci series recur in
nature and art. They can even be found in the workings of computer algorithms. When dividing any two consecutive
Fibonacci numbers, the quotient is very close to the value of the golden ratio. This is a kind of universal constant
seen in shell spiral patterns or pyramid designs. It is important to comprehend how to derive this series. It’s
crucial for numerous programming functions.
Iterative Approach to Generate Fibonacci Series in Java
Explanation
The iterative method of producing the Fibonacci series is fairly straightforward. We use
a loop to sum the two previous numbers to arrive at the desired number in this sequence. It is easy to understand
and also less time-consuming than other research methodologies.
Code Example
public class FibonacciIterative {
public static void main(String[] args) {
int n = 10; // Number of Fibonacci numbers to generate
int num1 = 0, num2 = 1;
System.out.print(num1 + ” ” + num2); // Print first two numbers
for (int i = 2; i < n; i++) {
int num3 = num1 + num2;
System.out.print(” ” + num3);
num1 = num2;
num2 = num3;
}
}
}
Step-by-Step Explanation
We start by defining the first two
Fibonacci numbers; let num1 = 0 and num2 = 1.
These two numbers we print.
For the next numbers in the sequence,
we use a for loop.
The next number (num3) is also
calculated within the loop, namely as a sum of num1 and num2.
We then update the variables num1 and
num2 to the next values in the sequence.
The loop goes on until the specified
number of Fibonacci numbers are produced.
Output
Time and Space Complexity
Time Complexity: O(n) because we
iterate through the loop n times.
Space Complexity: O(1) as we use
a constant amount of space.
Recursive Approach to Generate Fibonacci Series in Java
Explanation
The recursive approach involves the recursion principle, which means a function calls on
itself to solve a smaller part of the same problem. While this is quite elegant, this method results in redundant
calculations and, therefore, might be slow.
Code Example
public class FibonacciRecursive {
static int fib(int n) {
if (n <= 1)
return n;
return fib(n – 1) + fib(n – 2);
}
public static void main(String[] args) {
int n = 10; // Number of Fibonacci numbers to generate
for (int i = 0; i < n; i++) {
System.out.print(fib(i) + ” “);
}
}
}
Base Case and Recursive Call Explanation
Base Case: If n is 0 or 1, we
return n because the first two terms of the Fibonacci sequence are defined to be 0 and 1.
Recursive Call: For any other
value of n, we simply take the value of fib for n equals n-1 and n-2 and then add the values. This
calculates the Fibonacci number by dividing the problem into sub-problems and solving them in the same
manner.
Step-by-Step Explanation
The fib function is defined with an
input variable n, which is the integer data type.
It only returns a value if n is less
than or equal to 1.
Otherwise, it returns the result of
fib(n – 1) + fib(n – 2).
In the main method, using the ‘for’
loop with the iterations set from 0 to n, each Fibonacci number is printed using the fib function.
Output
Time and Space Complexity
Time Complexity: O(2^n) because
each call splits into two more calls, leading to an exponential growth in the number of calls.
Space Complexity: O(n) due to
the depth of the recursion stack.
Using Memoization to Optimise Recursive Fibonacci Series in Java
Explanation
Memoization is the technique of precomputing solutions to return when arguments recur in
a recursive algorithm. This saves time because the program discourages repeating calculations. However, in the
context of the Fibonacci series, memoization helps reduce the time complexity from exponential to
straight-line.
Code Example
public class FibonacciMemoization {
static long[] memo;
static long fib(int n) {
if (n <= 1) {
return n;
}
if (memo[n] != 0) {
return memo[n];
}
memo[n] = fib(n – 1) + fib(n – 2);
return memo[n];
}
public static void main(String[] args) {
int n = 10; // Number of Fibonacci numbers to generate
memo = new long[n + 1];
for (int i = 0; i < n; i++) {
System.out.print(fib(i) + ” “);
}
}
}
Step-by-Step Explanation
Initialisation: We declare and
initialise an integer array memo to store the calculated Fibonacci numbers.
Base Case: If n equals 0 or 1,
we return n as the first two terms in the sequence are 0 and 1.
Memoization Check: To compute a
Fibonacci number, we first check whether the number has been computed earlier and is available in the memo
array.
Recursive Call: If the number is
not in the memo array, we calculate it by calling fib(n—1) and fib(n—2 ) and putting this result in the memo
array.
Main Method: We then calculate
the n Fibonacci number and print the first n Fibonacci numbers.
Output
Time and Space Complexity
Time Complexity: O(n), because
each number is computed once.
Space Complexity: O(n), due to
the memoization array.
Dynamic Programming Method for Fibonacci Series in Java
Explanation
In a dynamic programming approach, a complex problem is sectioned into simpler
subproblems, and solutions to each subproblem are addressed systematically to arrive at a solution to the main
problem. This approach helps since we can host and use these solutions instead of repeatedly calculating them.
Memoization is somewhat like this; however, memoization is generally an iterative method.
Code Example
public class FibonacciDynamic {
static int fib(int n) {
int[] f = new int[n + 2];
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) {
int n = 10; // Number of Fibonacci numbers to generate
for (int i = 0; i < n; i++) {
System.out.print(fib(i) + ” “);
}
}
}
Step-by-Step Explanation
Array Initialisation: The first
step involves declaring an array f of
size n+2 to hold Fibonacci numbers.
Base Cases: We define f[0] as 0
and f[1] as 1.
Iteration: By using a for loop,
we can easily calculate each Fibonacci number from 2 to n, where the sum of any two preceding numbers gives
the result.
Main Method: We print the first
n of the Fibonacci sequence.
Output
Time and Space Complexity
Time Complexity: O(n), as each
Fibonacci number is computed once.
Space Complexity: O(n), because
of the array used to store Fibonacci numbers.
Generating Fibonacci Series Using For Loop in Java
Explanation
One of the easiest ways of generating the Fibonacci series in Java is to use a for loop.
It entails initialising the first two numbers, and then new numbers can easily be generated using a loop.
Code Example
public class FibonacciForLoop {
public static void main(String[] args) {
int n = 10; // Number of Fibonacci numbers to generate
long[] fib = new long[n];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < n; i++) {
fib[i] = fib[i – 1] + fib[i – 2];
}
for (int i = 0; i < n; i++) {
System.out.print(fib[i] + ” “);
}
}
}
Step-by-Step Explanation
Initialisation: We declare an
array called fib to store Fibonacci numbers and the initial numbers as 0 and 1, respectively.
For Loop: We perform a for loop
to calculate each Fibonacci number from 2 to n, where we get the sum of the two preceding numbers.
Output Loop: We use another for
loop to print the Fibonacci numbers.
Output
Time and Space Complexity
Time Complexity: O(n), because
the loop runs n times.
Space Complexity: O(n), due to
the array used to store the series.
Generating Fibonacci Series Using While Loop in Java
Explanation
This is another iterative method for generating the Fibonacci series. This method uses
the same concept as the normal use of the for loop, although it can be more versatile in some instances.
Code Example
public class FibonacciWhileLoop {
public static void main(String[] args) {
int n = 10; // Number of Fibonacci numbers to generate
int num1 = 0, num2 = 1;
int i = 2;
System.out.print(num1 + ” ” + num2);
while (i < n) {
int num3 = num1 + num2;
System.out.print(” ” + num3);
num1 = num2;
num2 = num3;
i++;
}
}
}
Step-by-Step Explanation
Initialisation: We initialise
the first two Fibonacci numbers, num1 and num2, as 0 and 1.
Print Initial Numbers: We print
the first two numbers.
While Loop: We use a while loop
to calculate and print the next Fibonacci numbers until we reach n.
Update Values: We update num1
and num2 inside the loop for the next iteration.
Output
Time and Space Complexity
Time Complexity: O(n), as the
loop runs n times.
Space Complexity: O(1), since we
use a fixed amount of space.
Checking if a Given Number is in the Fibonacci Series
Explanation
We often need to check if a given number is part of the Fibonacci series. To do this, we
can generate Fibonacci numbers until we reach or exceed the given number.
Code Example
public class CheckFibonacci {
public static boolean isFibonacci(int num) {
int a = 0, b = 1;
while (b < num) {
int c = a + b;
a = b;
b = c;
}
return b == num;
}
public static void main(String[] args) {
int num = 13; // Number to check
System.out.println(num + ” is a Fibonacci number: ” + isFibonacci(num));
}
}
Step-by-Step Explanation
Initialisation: We initialise
two variables, a and b, to 0 and 1.
While Loop: We use a while loop
to generate Fibonacci numbers until b is greater than or equal to num.
Check Condition: Inside the
loop, we check if b equals num. If so, the number is a Fibonacci number.
Return Result: We return true if
b equals num; otherwise, it is false.
Output
Time and Space Complexity
Time Complexity: O(n), as we
generate Fibonacci numbers until we reach or exceed the given number.
Space Complexity: O(1), because
we use a fixed amount of space.
Printing Fibonacci Series Up to a Given Number
Explanation
Sometimes, we want to generate the Fibonacci series up to a specific number rather than
a set number of terms. This approach is useful when we are not sure how many terms will be required to reach a
certain value. We use a loop to continue generating terms until we reach or exceed the given number.
Code Example
public class FibonacciUpToNumber {
public static void main(String[] args) {
int n = 50; // Print Fibonacci series up to this number
int num1 = 0, num2 = 1;
System.out.print(num1 + ” ” + num2);
while (num2 <= n) { int num3 = num1 + num2; if (num3 > n) break;
System.out.print(” ” + num3);
num1 = num2;
num2 = num3;
}
}
}
Step-by-Step Explanation
Initialisation: We start with
the first two Fibonacci numbers, num1 and num2, set to 0 and 1.
Print Initial Numbers: We print
these initial numbers.
While Loop: We use a while loop
to keep generating the next Fibonacci number (num3) until it exceeds n.
Condition Check: We break the
loop if the next number exceeds n.
Update Values: Inside the loop,
we update num1 and num2 to the next pair in the series.
Output
Time and Space Complexity
Time Complexity: O(n), as we
generate numbers until we reach or exceed n.
Space Complexity: O(1), since we
only use a fixed amount of space.
Handling User Input to Generate Fibonacci Series in Java
Explanation
We often need to generate the Fibonacci series based on user input. This approach allows
for dynamic generation of the series based on the user’s needs. We can achieve this by using the Scanner class in
Java to read user input.
Code Example
import java.util.Scanner;
public class FibonacciWithScanner {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter the number of Fibonacci terms: “);
int n = scanner.nextInt();
scanner.close();
long a = 0, b = 1;
System.out.println(“Fibonacci Series:”);
for (int i = 0; i < n; i++) {
System.out.print(a + ” “);
long c = a + b;
a = b;
b = c;
}
}
}
Step-by-Step Explanation
Scanner Initialisation: We
initialise a Scanner object to read user input.
User Prompt: We prompt the user
to enter the number of Fibonacci terms they want.
Read Input: We read the user
input and store it in the variable n.
Initialization: We initialise
the first two Fibonacci numbers, a and b, as 0 and 1.
For Loop: We use a for loop to
generate and print n Fibonacci numbers.
Update Values: Inside the loop,
we update a and b to the next pair in the series.
Output
Time and Space Complexity
Time Complexity: O(n), since the
loop runs n times.
Space Complexity: O(1), because
we use a fixed amount of space.
Practical Applications and Real-World Use Cases of Fibonacci Series in Java
Programming
The Fibonacci series has many practical applications in various fields. Here are a few
examples:
Computer Algorithms
Sorting Algorithms: Fibonacci
series can optimise certain sorting algorithms.
Search Algorithms: The Fibonacci
search technique is used to search sorted arrays.
Financial Modelling
Stock Market Analysis: Fibonacci
retracement levels help predict stock prices.
Algorithmic Trading: Algorithms
use Fibonacci ratios to make trading decisions.
Nature and Biology
Plant Growth: The pattern of
leaves, flowers, and branches often follows the Fibonacci series.
Animal Patterns: The series
appears in the arrangement of animal features, like the spirals of shells.
Mathematical Puzzles and Games
Recreational Math: Fibonacci
numbers are used in puzzles and mathematical games.
Game Development: Algorithms in
games sometimes use Fibonacci sequences to create patterns.
Time and Space Complexity
Understanding the time and space complexity of various approaches helps us choose the
right method for our specific needs.
Approach
Time Complexity
Space Complexity
Iterative
O(n)
O(1)
Recursive
O(2^n)
O(n)
Memoization
O(n)
O(n)
Dynamic Programming
O(n)
O(n)
For Loop
O(n)
O(n)
While Loop
O(n)
O(1)
Up to a Given Number
O(n)
O(1)
Handling User Input
O(n)
O(1)
Each method has its own strengths and weaknesses. Choosing The right one depends on the
specific requirements and constraints of our project.
Conclusion
In this blog, we explored various methods to generate the Fibonacci series in Java, each with its own advantages and use
cases. We started with the basic iterative and recursive approaches. We understood their simplicity and limitations.
By introducing memoization, we saw how to optimise the recursive method. It reduced its time complexity
significantly. Dynamic programming further demonstrated an efficient way to handle this problem. Both reduced time
and space complexity.
We also covered practical implementations using for and while loops and learned how to
handle user input. This made our programs dynamic. Finally, we discussed checking if a number belongs to the
Fibonacci series. We also explored real-world applications of this sequence in fields like computer algorithms, financial modelling and nature.
Understanding these different approaches enhances our problem-solving skills and
provides insights into selecting the most efficient method based on specific requirements. This comprehensive
exploration equips us with the knowledge to apply the Fibonacci series effectively in various programming
scenarios.
FAQs
How does the Fibonacci series work in Java?
The Fibonacci series in Java works by adding the two preceding numbers to generate the next number in the sequence. The series starts with 0 and 1. Each subsequent number is the sum of the two preceding ones.
Which method is most efficient for generating the Fibonacci series in Java?
The iterative approach and dynamic programming methods are considered the most efficient. This is due to their lower time and space complexity. Both methods ensure that each Fibonacci number is computed only once.
What is the time complexity of the recursive method for the Fibonacci series in Java?
The recursive method's time complexity is O(2^n), making it inefficient for large values of n. Each Fibonacci number is recomputed multiple times.
How can I check if the number is a Fibonacci number in Java?
We can use a loop. It will generate Fibonacci numbers up to the given number. Then, check if the number matches any of the generated Fibonacci numbers. The program will return true if the number is in the series. It will return false otherwise.
What are the practical applications of the Fibonacci series in Java?
The Fibonacci series has practical applications in computer algorithms. It is used in financial modelling, nature, biology, and even game development. It helps to optimise algorithms. It can predict stock prices. The series models natural patterns and solves mathematical puzzles.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
