Using Memoization in Groovy Dynamic Programming in a Dynamically Typed Language by Venkat Subramaniam Venkat explores the immense time-space tradeoffs of memoization, and explains how Groovy makes memoization easy. “Dynamic programming” is intriguing for a few reasons. The combined words do not directly refer to anything dynamic or programming, at least not in the sense attached to those words individually today. It is an algorithmic technique that takes a counterintuitive approach to realizing blazingly fast computation. We will explore this technique here and quickly implement an example using the facility available in Groovy. In a recursive solution we solve a problem using solutions to subproblems. Dynamic programming takes this to the extreme, by using overlapping recursive solutions. In other words, the solution to a sub-problem is used multiple times in the solution to the problem. Take the Fibonacci series, 1, 1, 2, 3, 5, 8, 13, 21, ..., for example. The number at any position in this series can be expressed as a recursion: Fib(position) is 1 if position 2 Fib(position - 1) + Fib(position - 2) if position = 2 for position = 0 This recursion is simple to express, but terrible in performance if naively implemented, because it uses overlapping solutions. For example, to find the value at position 5, we’d perform Fib(4) + Fib(3). But Fib(3) would also be computed in the solution to Fib(4). Likewise, Fib(2) would appear in the solution to Fib(4) and also in solution to Fib(3). These overlapping reevaluations make the computational complexity of this recursion exponential, that is, O(2^position). That’s bad, but only if we actually perform the reevaluations. If instead we store a computation the first time and reuse it each time it’s needed, we can reduce this to linear complexity, that is, to a time complexity of O(position). It’s a space vs. time tradeoff, in favor of gaining speed and implementation simplicity. And this is memoization, a way to store away the solutions and reuse them to speed up the dynamic programming algorithmic technique. Though we look at a simple problem here, the Fibonacci series, dynamic programming and memoization are used in a number of day-to-day problems, such as finding the shortest driving distance between cities, maximizing profit in sales, minimizing cost and reducing waste, etc. It’s used in a broad range of optimization problems where the goal is to choose a best solution among different possible solutions. Let’s implement the algorithm for the Fibonacci series as a simple recursion first, and measure its time. Then let’s use the memoization technique to speed it up. Here’s the function to compute the Fibonacci value at a given position. PragPub January 2013 17