Created
July 5, 2016 07:49
-
-
Save meghakrishnamurthy/331bd9addab3dbb1b6a23802b1c6845e to your computer and use it in GitHub Desktop.
Fibonacci - Recursive and Iterative implementation in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package megha.codingproblems.general; | |
/** | |
* Fibonacci program - Both iterative and recursive versions | |
* Fibonacci series - 1,1,2,3,5,8,13.... | |
* | |
* @author megha krishnamurthy | |
* | |
*/ | |
public class Fibonacci { | |
/** | |
* Iterative implementation for nth fibonacci number | |
* Time complexity - O(n) | |
* Space complexity - O(1) | |
* | |
* @param n | |
* @return | |
*/ | |
public int fibonacciIterative(int n) { | |
if(n <= 1) { | |
return n; | |
} | |
int fib = 1; | |
int prevFib = 1; | |
for(int i=2; i<n; i++) { | |
int temp = fib; | |
fib+= prevFib; | |
prevFib = temp; | |
} | |
return fib; | |
} | |
/** | |
* Recursive implementation for nth fibonacci number | |
* Time complexity - O(n) | |
* Space complexity - O(n) | |
* | |
* @param n | |
* @return | |
*/ | |
public int fibonacciRecursive(int n) { | |
if(n <= 1) { | |
return n; | |
} | |
return fibonacciRecursive(n-1) + fibonacciRecursive(n-2); | |
} | |
public static void main(String args[]) { | |
Fibonacci fib = new Fibonacci(); | |
System.out.println("Iterative version:"); | |
System.out.println(fib.fibonacciIterative(5)); | |
System.out.println(fib.fibonacciIterative(10)); | |
System.out.println(fib.fibonacciIterative(20)); | |
System.out.println(fib.fibonacciIterative(30)); | |
System.out.println("Recursive version:"); | |
System.out.println(fib.fibonacciRecursive(5)); | |
System.out.println(fib.fibonacciRecursive(10)); | |
System.out.println(fib.fibonacciRecursive(20)); | |
System.out.println(fib.fibonacciRecursive(30)); | |
} | |
} |
I also ended up here with a google search. O(2^n) is defiantly the correct complexity for recursive Fibonacci
The recursive Fibonacci can be O(n) by adding a simple cache:
public int fibonacciRecursive(int n) {
return fibonacciRecursiveCache(new int[n+1], n);
}
public fibonacciRecursiveCache(int[] cache, int n) {
if (n <= 1) {
return n;
}
if (cache[n] == 0) {
cache[n] = fibonacciRecursiveCache(cache, n-1) + fibonacciRecursiveCache(cache, n-2);
}
return cache[n];
}
The recursive Fibonacci can be O(n) by adding a simple cache:
public int fibonacciRecursive(int n) { return fibonacciRecursiveCache(new int[n+1], n); } public fibonacciRecursiveCache(int[] cache, int n) { if (n <= 1) { return n; } if (cache[n] == 0) { cache[n] = fibonacciRecursiveCache(cache, n-1) + fibonacciRecursiveCache(cache, n-2); } return cache[n]; }
Actually, the Fibonacci version using memoization would look like this
public static void main(String[] args) {
int n = 3;
Integer [] memo = new Integer [n];
int result = fibonacci(n, memo);
System.out.println(result);
}
private static int fibonacci(int n, Integer[] memo) {
// TODO Auto-generated method stub
int result;
if (memo[n-1]!= null ) {
return memo[n-1];
}else {
if(n <= 2) {
result = 1;
}else {
result = fibonacci(n-1, memo) + fibonacci(n-2, memo);
}
memo[n-1] = result;
}
return result;
}
You gotta check if the memo already contains the result for a specific 'n', otherwise you need to compute it and store it in the memo array. This should avoid computing the same thing over and over again
The recursive implementation's time complexity is about O(1.6^n), to be somewhat more precise. Still exponential, still untenable.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I also reached here from google search. You're all right! He needs to fixe
the comments inside his code. His recursive Fibonacci algorithm is the naive one
which is O(2^n).