Example: Fibonacci

Fibonacci is defined as:

• F(n) = F(n-1) + F(n-2)
• F(0) = 0
• F(1) = 1

int fib(n) {
    if (n<2) {
        return n;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

Note that F(4) = F(3) + F(2) = F(2) + F(1) + F(2) => duplicate operation. We can use Memoization to store the results that we have already computed. This approach sacrifices space for speed.

Map<Integer, Integer> cache = new HashMap<>();
int fib(int n) {
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    int res = n < 2 ? n : fib(n-1) + fib(n-2);
    cache.put(n, res);
    return res;
}