if (base condition) {// base condition with iterative solution
return <some simple iterative expression>
}
else {// recursive case
some work before call()
recursive call()
some work after call()
}
Fibonacci using Dynamic Programming in Java and Kotlin
Carvia Tech  August 03, 2019  3 min read  131 views
Before starting Dynamic Programming, we must get familiar with recursion first.
Recursion
In recursion, we simply a complex problem by breaking it down into simpler subproblems in a recursive manner. If a problem can be composed off subproblems, then it could be a good candidate for recursion.
Few examples of recursive problems are:

Calculation of Fibonacci number

Calculating factorial of a given number
Solution to a recursive problem is built using solution to its subproblems. Recursive solutions can be broadly divided into two categories:
 Bottomup recursion

Here we start with knowing how to solve the problem for the simple case, like with only 1 element for factorial and then for 2 elements. Basically we build the solution for one case off of the previous case.
 Topdown recursion

We start with dividing the problem for case N into subproblems till we achieve the solution.

Recursion is helpful in writing complex algorithms in easy to understand manner.

Normally iterative solutions provide better efficiency compared to recursive one because of so much overhead involved in executing recursive steps.
Calculating Fibonacci using Recursion
For example, we would use the following code to calculate the Fibonacci series using recursion
fun fibonacci(n: Int): Long {
if (n == 0) return 0
if (n == 1) return 1
return fibonacci(n  1) + fibonacci(n  2)
}
public class Fibonacci {
public int fib(int n) {
if (n <= 1) { (1)
return n;
} else { (2)
return fib(n  1) + fib(n  2);
}
}
}
1  base condition 
2  recursive condition 
Computing the nth
Fibonacci number depends on the solution of previous n1
numbers, also each call invokes two recursive calls. This means that the Time complexity of above fibonacci program is Big O (2^{n}) i.e. exponential. That’s because the algorithm’s growth doubles with each addition to the data set.
Exponential runtime complexity
Time complexity of an algorithm is Big O (2^{n}) i.e. exponential when its growth doubles with each addition to the input data set. It is exactly opposite to Big O (log n) where problem size is reduced to half on each successive iteration.

Dynamic Programming
Dynamic Programming is a powerful optimization technique, where a recursive problem can be solved in O (n^{2}) or O (n^{3}) where a naive approach would take exponential time O (2^{n})
The optimization in Dynamic Programming is achieved by caching the intermediate results for the future calls.
If we run the previous fibonacci program, input of 50 will take around 1 minute on a average modern hardware.
Now, we will write the same fibonacci program using Dynamic Programming:
class Fibonacci {
private val cache: MutableMap<Int, Long> = HashMap()
fun cal(n: Int): Long {
if (n == 0) return 0
if (n == 1) return 1
return when {
cache.containsKey(n) > cache[n]!!
else > {
cache[n] = cal(n  1) + cal(n  2)
cache[n]!!
}
}
}
}
public class Fibonacci {
final int max = 10000;
int[] fib = new int[max];
int fibonacci(int num) {
if (num == 0) return 0;
if (num == 1) return 1;
if (fib[num] != 0) {
return fib[num]; (1)
}
fib[num] = fibonacci(num  1) + fibonacci(num  2); (2)
return fib[num];
}
}
1  return the cached result, if already available. 
2  cache the result of computation for future use. 
You can try to run the above example on your machine, even 1000th
Fibonacci number will be calculated in a fraction of millisecond.
In nutshell, Dynamic Programming is an optimized recursive technique where you cache the results for use in future calls. You can always start with a normal recursive approach first and then add the caching part later on.
Top articles in this category:
 ION Trading Java Interview Questions
 RBS Java Programming Interview Questions
 Citibank Java developer interview questions
 Java Concurrency Interview Questions and Answers
 Top 50 Multithreading Java Interview Questions for Investment Bank
 Goldman Sachs Java Interview Questions for Senior Developer
 BlackRock Top Java Interview Questions: Investment Banking Domain
Find more on this topic:
Java Interviews
Interview  Product Companies, eCommerce Companies, Investment Banking, Healthcare Industry, Service Companies and Startups.
Last updated 1 week ago
Recommended books for interview preparation:
Similar Posts
 Spring Boot with GMAIL SMTP
 Mandrill emails in Spring Boot Java
 Top 30 Hibernate and Spring Data JPA interview questions
 Generating variable length secure key/secret in Java
 Reverse the bits of a number and check if the number is palindrome or not
 MD5 and SHA256 in Java Kotlin and Android
 Spring Security 5  There is no PasswordEncoder mapped for the id
 Interthread communication in Java
 What are different thread states in Java
 Static method synchronization aka Class Lock in Java
Provide email address to subscribe to this blog.