Fibonacci Series in Java [ Iterative Method ]
Our first and most basic way to calculate a fibonacci series program in Java will be using an iterative method. As the name suggests, we will iterate the series using a loop. Let’s dig deeper in the following example.Example
public class IterativeFibonacci {
public static void fibonacci(int MAX) {
int firstNumber = 0;
int secondNumber = 1;
int fibonacci = '\0';
System.out.print(firstNumber + " ");
System.out.print(secondNumber + " ");
for (int i = 2; i < MAX; i++) {
fibonacci = firstNumber + secondNumber;
System.out.print(fibonacci + " ");
firstNumber = secondNumber;
secondNumber = fibonacci;
}
}
public static void main(String[] args) {
System.out.println("Print Fibonacci Series Using Iterative Method");
int MAX = 15;
fibonacci(MAX);
}
}
Output
Explanation
In the above example, we are using a method called “fibonacci” to print the fibonacci series iteratively. The variable MAX stores the total number of fibonacci numbers you want to print. The two variables firstNumber and secondNumber store the first two fibonacci numbers respectively. Then the for loop begins with i = 2, because first and second fibonacci numbers are already printed. In each iteration, the first and the second number are updated to keep the series going. The loop ends, as it approaches the MAX limit i-e; i < MAX.
Fibonacci Series Using Recursion in Java
Since you’re familiar with the iterative method, let’s compute fibonacci series using recursion in Java.Example
public class RecursiveFibonacci {
// recursive method to return the fibonacci series
public static int fibonacci(int MAX) {
// base case
if (MAX <= 1) {
return MAX;
}
// recursive call
else {
// calculate the last two fibonacci numbers recursively
return fibonacci(MAX - 2) + fibonacci(MAX - 1);
}
}
public static void main(String[] args) {
System.out.println("Print Fibonacci Series Using Recursion in Java");
int MAX = 10;
for (int i = 0; i < MAX; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}
Output
Explanation
First we define the MAX number of digits for the recursive fibonacci series in Java. Then we call the recursive function called “fibonacci”. As you know, to use recursion in Java, we have to define and deal with 2 cases. The first is the base case, and the other is the recursive case. In the base case, we check if the MAX value is less than or equal to 1. If it is true, then the same number is returned (imagine the first two digits of fibonacci 0 and 1). That’s how the base numbers are calculated. In the recursive call, we calculate the last two numbers of the series by reducing one and two from MAX. The fibonacci method will keep calling itself till it reaches the last two digits (0 and 1), add them and then keep adding the last two digits till it reaches MAX.Optimizing Fibonacci Series in Java with Memoization
So, you’ve already mastered the classic ways to generate Fibonacci numbers using recursion and iteration. But what if I told you there’s an even smarter way? That’s where memoization comes in! Let’s explore how this technique can speed up Fibonacci calculations and make our code much more efficient.
What is Memoization?
Memoization is a technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. It’s like telling Java, "Hey, we’ve already calculated this number before—no need to do it again!" This is especially useful for recursive Fibonacci implementations, where the same function is called multiple times with the same arguments.
Why is Memoization Needed?
Let’s take a quick look at the classic recursive Fibonacci approach:
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Looks simple, right? But there’s a hidden problem! This method recalculates the same Fibonacci values multiple times, making it super slow for large n. For instance, calling fibonacci(40) results in over a billion redundant calculations. Yikes!
Optimizing Fibonacci with Memoization
Instead of recalculating values repeatedly, let’s store already computed Fibonacci numbers in an array and reuse them when needed.
import java.util.HashMap;
public class FibonacciMemoization {
private static HashMap memo = new HashMap<>();
public static int fibonacci(int n) {
if (n <= 1) return n;
// Check if the value is already computed
if (memo.containsKey(n)) {
return memo.get(n);
}
// Compute and store the value in the memo table
int result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
int n = 40;
System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
}
}
With memoization, we reduce the time complexity from O(2^n) to O(n). This means calculating fibonacci(40) takes milliseconds instead of minutes!
How Does This Work?
Every time we compute a Fibonacci number, we store it in a HashMap. Before making a new recursive call, we check if the value is already in our map. If it is, we return it instantly—no need to recompute.
GO TO FULL VERSION