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;
        }
    }
}