Memoization

I invite you to work with me on a small math problem. Grab a paper and pencil. All set? OK, here we go. What’s 321 + 174? Without a calculator on hand it’s not something I can answer spontaneously, and if you need a moment to find the answer, that’s perfectly normal.

Did you find it? If you wrote down 495 you got it without any errors. Good job.

Now, one more question. What’s 321 + 174? Now, you answered that in a snap, didn’t you? How did you get so fast so quickly?

It’s ok to admit, you looked up the result from the previous computation. That’s pretty smart; you wouldn’t redundantly compute the expression that you evaluated only a moment ago. That’s memoization when done in code—we don’t want our programs to recompute functions that were executed already for the same input, provided the output will be the same no matter how many times we call for the same input. By using saved values we can avoid recomputation and make executions faster. A caveat, though—memoization may only be used for pure functions, which are functions with no side effects.

In dynamic programming, an algorithmic technique, the problem is solved recursively using solutions to subproblems, but in a way that the results of the subproblem are memoized and reused. This technique brings the computational complexity of problems from exponential to linear and results in huge performance gains while keeping the code expressive.

Kotlin doesn’t directly support memoization, but we can build it with the tools you’ve learned so far. We’ll implement memoization in two different ways in Kotlin: one like the solution provided in the Groovy language’s library and one using Kotlin delegates.

Repetitive computation

We’ll consider two problems in this chapter to illustrate memoization, a simple one first and then something a bit more complicated.

The first problem, the Fibonacci number, has been beaten to death in programming examples. One reason, and why we’ll use it here, is the problem is very simple, well understood, and we can keep our eyes on the solution without getting dragged into the complexity of a problem. Once we learn how to use memoization with this simple problem, we’ll apply it to the rod-cutting problem, but we’ll discuss that later.

Let’s implement a simple recursion in Kotlin to find the Fibonacci number.