Fibonacci.java
package ch.hslu.exercises.sw01.ex4;
import java.util.HashMap;
public final class Fibonacci {
private static final HashMap<Long, Long> ALREADY_COMPUTED_RESULTS = new HashMap<>();
private Fibonacci() {
}
public static long fiboRec1(final long n) {
//Rekursionsbasis
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
//Rekursionsvorschrift
return fiboRec1(n - 2) + fiboRec1(n - 1);
}
public static long fiboRec2(final long n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (ALREADY_COMPUTED_RESULTS.containsKey(n)) {
return ALREADY_COMPUTED_RESULTS.get(n);
} else {
long resultFirstRecCall = fiboRec1(n - 1);
long resultSecondRecCall = fiboRec1(n - 2);
if (!ALREADY_COMPUTED_RESULTS.containsKey(n - 1)) {
ALREADY_COMPUTED_RESULTS.put(n - 1, resultFirstRecCall);
}
if (!ALREADY_COMPUTED_RESULTS.containsKey(n - 2)) {
ALREADY_COMPUTED_RESULTS.put(n - 2, resultSecondRecCall);
}
return resultFirstRecCall + resultSecondRecCall;
}
}
public static long fiboIter(final long n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
} else {
long firstTerm = 1;
long secondTerm = 1;
for (int i = 3; i <= n; i++) {
long formerFirst = firstTerm;
firstTerm = secondTerm;
secondTerm = formerFirst + secondTerm;
}
return secondTerm;
}
}
}