Imagine this was a problem like the rod cutting problem (the Groovy solution to which is presented in Programming Groovy 2nd Edition [U1]) where we want to measure the maximum profit from the retail sale of different sizes of rods. For a large size of rod, say 500 inches, it would take hours or even days to compute, during which time the market may well fluctuate before we find out the best ways to sell the inventory on hand, rendering the solution totally useless. The degradation in performance came from calling the functions over and over. For example, just for the small position of 5, the fib function was invoked 15 times, and for the position of 40, it was called a whopping 331,160,281 times. Let’s turn to memoization for help. When the fib function is invoked, we could look up the value in a hashmap and evaluate the logic only if the value is not present. First we need a hashmap to store the values let’s create it and seed it with the two initial values. fibSeries = [0: BigInteger.ONE, 1: BigInteger.ONE] Now, we can modify the fib function to use this hashmap. def fib(position) { if(!fibSeries.containsKey(position)) fibSeries[position] = fib(position - 1) + fib(position - 2) fibSeries[position] } If the value for the given position is not in the hashmap, we compute it and store it in the collection. Then we simply return the value stored. If the value is already present, then we skip the computation. Let’s invoke the modified version of the function and measure the time to execute. timeit(5) { position - fib(position) } timeit(5) { position - fib(position) } timeit(40) { position - fib(position) } timeit(42) { position - fib(position) } The code to call the functions are the same as before, but the time it takes is quite different. Fib(5): 8, time: 0.02 sec Fib(5): 8, time: 0.00 sec Fib(40): 165580141, time: 0.00 sec Fib(42): 433494437, time: 0.00 sec The first call for position 5 took about the same time as the previous version. The subsequent calls for positions of 5, 40 and 42 took really no noticeable time. They appear faster than the first invocation, but that’s because the JVM has warmed up and taken care of JIT optimizations in the first call. If we compare the results of the two versions side-by-side, the values at respective positions are the same, but the computation time is a world apart. Compared to the 15 times the fib function was called for the position of 5, in this version it is called only 9 times. For the position of 40, on the other hand, the number of calls went down from 331,160,281 times to a mere 79 calls, thanks to memoization. PragPub January 2013 19