Skip to content

Instantly share code, notes, and snippets.

@shailrshah
Created October 15, 2017 16:52
Show Gist options
  • Select an option

  • Save shailrshah/3fb86aa5548932cd2da332d1ea6394ff to your computer and use it in GitHub Desktop.

Select an option

Save shailrshah/3fb86aa5548932cd2da332d1ea6394ff to your computer and use it in GitHub Desktop.
Return the nth number in the Fibonacci Sequence
import java.util.Map;
import java.util.HashMap;
class Fib {
static long getFibIterative(int n) {
if(n < 2)
return n;
long a = 0, b = 1, c = a + b;
for(int i = 2; i <= n; c = a+b, a = b, b = c, i++);
return c;
}
static long getFibRecursive(int n) {
return n < 2 ? n : getFibRecursive(n-1) + getFibRecursive(n-2);
}
static Map<Integer, Long> map = new HashMap<>();
static long getFibRecursiveEnhanced(int n) {
if(n < 2)
return n;
Long value = map.get(n);
if(value == null){
long ans = getFibRecursiveEnhanced(n-1) + getFibRecursiveEnhanced(n-2);
map.put(n, ans);
value = ans;
}
return value;
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
for(int i = 0; i < n; i++)
System.out.print(getFibIterative(i) + " ");
// System.out.println();
// for(int i = 0; i < n; i++)
// System.out.print(getFibRecursive(i) + " ");
System.out.println();
for(int i = 0; i < n; i++)
System.out.print(getFibRecursiveEnhanced(i) + " ");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment