In this post we’ll look at Memo which is a Scalaz goodie to add memoization to your program. We’ll recap what memoization is, write a recursive function to calculate Fibonacci numbers, and then add memoization to it using `Memo`

.

## What is Memoization?

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.^{[1]}

## Fibonacci (without Memo)

1 | @ def fibo(n: Int): Int = { |

So here’s the non-memoized recursive `fibo`

which calculates the n^{th} Fibonacci number. The issue here is that it’ll recalculate the Fibonacci numbers a lot of times and therefore cannot be used for large values of n.

## Fibonacci (with Memo)

1 | @ import scalaz._ |

Here’s the memoized version using Scalaz `Memo`

. We are using an immutable, hash map-backed memo. The `immutableHashMapMemo`

method takes a partial function defining how we construct the memo. In our case, if the value of n is not 0 or 1, we try looking up the value in the memo again. We recurse until we reach 0 or 1. Once that happens and our recursion returns, the resultant value is cached in an `immutable.HashMap`

.

## Conclusion

Memoization is a great way to optimize your programs. In this post we used an immutable hash map memo. There are other types of memos applying different strategies to cache their results. The `Memo`

companion object is the place to look for an appropriate memo that suits your needs.