/// Returns the nth Fibonacci number, remembering previous results.
long fibFast(int n) {
    Map<Integer, Long> memo = new HashMap<>();
    return fibFast(n, memo);
}

long fibFast(int n, Map<Integer, Long> memo) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    if (n <= 1) {
        return n;
    }

    memo.put(n, fibFast(n - 1, memo) + fibFast(n - 2, memo));
    return memo.get(n);
}

void main() {
    IO.println(fibFast(50));
    IO.println(fibFast(90));
}

// From Groundwork, chapter 12 (ch12-recursion-and-problem-solving), box 8.
// This example is from Groundwork, licensed CC BY-NC-SA 4.0.
// Run with: java ch12_08.java