Memoization is the technique of caching repeated calculations thereby achieving a significant increase in the speed of computation.

I will take an example in illustrating this:

Here is the code to calculate fibonacci number at a given position which uses the concept of recursion:

private static BigInteger fibonacciNormal(long n) {

if (n <= 0) {

return BigInteger.ZERO;

}

if (n == 1 || n == 2) {

return BigInteger.ONE;

}

return fibonacciNormal(n-1).add(fibonacciNormal(n-2));

}

The problem with the above code is that it becomes too slow as you provide a bigger value of input n. The reason is that there are repeated calculations being done which can be avoided by caching them.

The following code used the concept of memoization by avoiding the repeated calculations by caching the results.

private static BigInteger fibonacci(long n) {

if (n <= 0) {

return BigInteger.ZERO;

}

if (n == 1 || n == 2) {

return BigInteger.ONE;

}

// See if we already computed fibonacci(n)

BigInteger result = fibonacciCache.get(n);

if (result == null) {

result = fibonacci(n-1).add(fibonacci(n-2));

// Update the cache

fibonacciCache.put(n, result);

}

return result;

}