$show=/label

Java Fibonacci Series Recursive Optimized using Dynamic Programming

SHARE:

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.

Java Fibonacci Series Recursive Optimized using Dynamic Programming


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.

Print the Fibonacci series using recursive way with Dynamic Programming-1


3rd fibonacci number is calculated twice.


Print the Fibonacci series using recursive way with Dynamic Programming-2

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.

Find the nth Fibonacci number using recursive way Using Dynamic Programming

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.

GitHub

Java Programs

HashMap Examples

COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,37,ArrayList,16,Arrays,16,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,5,Collections,28,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,6,Core Java,93,Corona India,1,Create,2,CSS,1,Date,3,Date Time API,35,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,3,Fast,1,Files,13,Float,1,Font,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,30,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,Java 8,105,Java 8 Difference,2,Java 8 Stream Conversions,2,java 8 Stream Examples,3,Java 9,1,Java Conversions,11,Java Design Patterns,1,Java Files,1,Java Program,3,Java Programs,104,java.lang,5,java.util. function,1,jQuery,1,Kotlin,11,Kotlin Conversions,6,Kotlin Programs,10,Lambda,1,lang,29,Leap Year,1,live updates,1,LocalDate,1,Logging,1,Mac OS,2,Math,1,Matrix,5,Maven,1,Method References,1,Mockito,1,MongoDB,3,New Features,1,Operations,1,Optional,6,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,2,Sort,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Streams,27,String,58,String Programs,12,String Revese,1,Swing,1,System,1,Tags,1,Threads,11,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,3,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Fibonacci Series Recursive Optimized using Dynamic Programming
Java Fibonacci Series Recursive Optimized using Dynamic Programming
A quick guide to write a java program print Fibonacci series and find the nth Fibonacci number using recursive optimized using dynamic programming.
https://1.bp.blogspot.com/-ArOfNCwnFGY/X_Qml0XUwuI/AAAAAAAADMs/MAcLoKccmx4nDXtzjJFCvWOlz7uQt95FQCLcBGAsYHQ/w400-h280/Java%2BFibonacci%2BSeries%2BRecursive%2BOptimized%2Busing%2BDynamic%2BProgramming.png
https://1.bp.blogspot.com/-ArOfNCwnFGY/X_Qml0XUwuI/AAAAAAAADMs/MAcLoKccmx4nDXtzjJFCvWOlz7uQt95FQCLcBGAsYHQ/s72-w400-c-h280/Java%2BFibonacci%2BSeries%2BRecursive%2BOptimized%2Busing%2BDynamic%2BProgramming.png
JavaProgramTo.com
https://www.javaprogramto.com/2021/01/%20java-fibonacci-recursive-optimized.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2021/01/%20java-fibonacci-recursive-optimized.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content