-
-
Save mang0kitty/6c898871217ec99eff360d5a8c54bf40 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(2^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)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I changed the time complexity of recursive Fibonacci from O(n) to O(2^n) or exponential.