A quick guide to write a java program print Fibonacci series and find the nth Fibonacci number using recursive optimized using dynamic programming.
1. Overview
In this article, we will learn how to print the fibonacci series and find the nth fibonacci number using recursive approach.
Printing the Fibonacci series be done using the iterative approach using while and for loop.
In the following sections we will try to run the program for below scenarios.
- Print the fibonacci series for the given number
- Find the nth fibonacci number
In each approach, we will try to see the amount of time taken to process the logic and how it can be optimized using dynamic programming memoization technique.
2. Print the Fibonacci series using recursive way
Below program to display the first n Fibonacci number using recursive approach. For each input, we are going to print the time taken and compare for different inputs.
package com.javaprogramto.programs.numbers.fibonacii;
import java.time.Instant;
public class PrintFibonaciiSeriesRecursive {
public static void main(String[] args) {
long fibResult = 0;
System.out.println("First 30 fibonacii series numbers : ");
long startTime = Instant.now().toEpochMilli();
for (int i = 1; i < 30; i++) {
fibResult = fibonacii(i);
System.out.print(fibResult + " ");
}
long endTime = Instant.now().toEpochMilli();
System.out.println("\nExecution time " + (endTime - startTime) + " ms");
System.out.println("\nFirst 50 fibonacii series numbers : ");
startTime = Instant.now().toEpochMilli();
for (int i = 1; i < 50; i++) {
fibResult = fibonacii(i);
System.out.print(fibResult + " ");
}
endTime = Instant.now().toEpochMilli();
System.out.println("\nExecution time " + (endTime - startTime) + " ms");
}
// fibonacii recursive
private static long fibonacii(long n) {
if (n <= 2) {
return 1;
}
long fibNumber = fibonacii(n - 1) + fibonacii(n - 2);
return fibNumber;
}
}
Output:
First 30 fibonacii series numbers : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 Execution time 6 ms First 50 fibonacii series numbers : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 Execution time 53397 ms
From the output, we can understand that to print first 30 fibonacci numbers it took just 6 milli seconds but to print the first 50, it took around 54 seconds.
Time complexity: O(2^n)
Space complexity:
3. Print the Fibonacci series using recursive way with Dynamic Programming
In the above program, we have to reduce the execution time from O(2^n).
If you observe the above logic runs multiple duplicates inputs.
Look at the below recursive internal calls for input n which is used to find the 5th Fibonacci number and highlighted the input values that are processed by our function multiple times.
2nd Fibonacci number is calculated 3 times.
3rd fibonacci number is calculated twice.
If the input value is 50 there are many inputs are reprocessed for the same inputs which kills the system.
From these analysis, if we can store these values in the memory we can avoid reprocessing them and retrieve the values from memory. This process is called as memoization.
Memoization make sure alway it runs for the different inputs and not for the same inputs again. Instead, gets the values from previous results from memory.
We can use HashMap for storing the intermediate key value pairs.
The below is the optimized program that takes less time for bigger inputs.
package com.javaprogramto.programs.numbers.fibonacii;
import java.time.Instant;
import java.util.Map;
import org.apache.commons.collections4.map.HashedMap;
public class PrintFibonaciiSeriesRecursiveOptimized {
public static void main(String[] args) {
long fibResult = 0;
Map<Integer, Long> memory = new HashedMap<>();
System.out.println("First 30 fibonacii series numbers : ");
long startTime = Instant.now().toEpochMilli();
for (int i = 1; i < 30; i++) {
fibResult = fibonacii(i, memory);
memory.clear();
System.out.print(fibResult + " ");
}
long endTime = Instant.now().toEpochMilli();
System.out.println("\nExecution time " + (endTime - startTime) + " ms");
memory.clear();
System.out.println("\nFirst 50 fibonacii series numbers : ");
startTime = Instant.now().toEpochMilli();
for (int i = 1; i < 50; i++) {
fibResult = fibonacii(i, memory);
memory.clear();
System.out.print(fibResult + " ");
}
endTime = Instant.now().toEpochMilli();
System.out.println("\nExecution time " + (endTime - startTime) + " ms");
}
// fibonacii recursive
private static long fibonacii(int n, Map<Integer, Long> memory) {
if(memory.get(n) != null) {
return memory.get(n);
}
if (n <= 2) {
return 1;
}
long fib = fibonacii(n - 1, memory) + fibonacii(n - 2, memory);
memory.put(n, fib);
return fib;
}
}
Output:
First 30 fibonacii series numbers : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 Execution time 2 ms First 50 fibonacii series numbers : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 Execution time 3 ms
From the above output, you can see the for bigger inputs just took 3ms which is fabulous. We brought down to 3 milli seconds from 54 seconds.
This is the power of the dynamic programming technique.
4. Find the nth Fibonacci number using recursive way
The below example program to get the nth fibonacci number from the series recursively.
package com.javaprogramto.programs.numbers.fibonacii;
import java.time.Instant;
public class FindFibonaciiNumberRecursive {
public static void main(String[] args) {
long startTime = Instant.now().toEpochMilli();
long finResult = fibonacii(30);
long endTime = Instant.now().toEpochMilli();
System.out.println("30th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
startTime = Instant.now().toEpochMilli();
finResult = fibonacii(50);
endTime = Instant.now().toEpochMilli();
System.out.println("50th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
}
// fibonacii recursive
private static long fibonacii(long n) {
if (n <= 2) {
return 1;
}
return fibonacii(n - 1) + fibonacii(n - 2);
}
}
Output:
30th fiboncaii number - 832040 execution time 5 ms 50th fiboncaii number - 12586269025 execution time 34413 ms
Take taken for 30th fibonacci number is 5 ms
50th Fibonacci number is 34 seconds.
Time Complexity - O(2^n)
Space Complexity - O(2^n)
5. Find the nth Fibonacci number using recursive way Using Dynamic Programming
Next, let us simplify the above code using memoization technique using hashmap.
package com.javaprogramto.programs.numbers.fibonacii;
import java.time.Instant;
import java.util.HashMap;
import java.util.Map;
public class FindFibonaciiNumberRecursiveOptimized {
public static void main(String[] args) {
Map<Integer, Long> memory = new HashMap<>();
long startTime = Instant.now().toEpochMilli();
long finResult = fibonacii(30, memory);
long endTime = Instant.now().toEpochMilli();
System.out.println("30th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
// clearing the memoization map
memory.clear();
startTime = Instant.now().toEpochMilli();
finResult = fibonacii(50, memory);
endTime = Instant.now().toEpochMilli();
System.out.println("50th fiboncaii number - " + finResult + " execution time " + (endTime - startTime) + " ms");
}
// fibonacii recursive
private static long fibonacii(int n, Map<Integer, Long> memory) {
if(memory.get(n) != null) {
return memory.get(n);
}
if (n <= 2) {
return 1;
}
long fib = fibonacii(n - 1, memory) + fibonacii(n - 2, memory);
memory.put(n, fib);
return fib;
}
}
Output:
30th fiboncaii number - 832040 execution time 0 ms 50th fiboncaii number - 12586269025 execution time 0 ms
In this approach, if we want to calculate the 5th Fibonacci number from series, it calculates the only the lest side values from the recursive tree.
So, it reduces the logic execution from 2^n to n times.
Time Complexity : O(2^n)
Space Complexity : O(n) because it still holds the n level runtime stack.
6. Conclusion
In this article, we have seen how to implement the fibonacci series and find nth fibonacci number using recursive approach and optimized way using dynamic programming technique.
Why would anyone do the first example? Calling a recursive function inside a for loop is just wrong. The for loop & recursion are meant to replace each other.
ReplyDeleteYou would just call the function passing in an output mechanism. You print each number just before you return from the function with the computed value.
Hello Joseph,
ReplyDeleteThe first example is to show the execution time for smaller nth fibonacci number and larger nth fibonacii number.
But in the real time, it is really not suggestible to use. Here the intention is show the execution timings.
The later section has shown the best ways to tackle the time complexity.