This is about how to implement memoization trick while keep your code clean in Python.

Memoization

Memoization is a way to speedup the computation of your recursive function f(n) in which the result of f(n) is derived from f(n-1). The trick is once f(n-1) is computed, we memorize its result for later uses so that we can skip any costly redundant function calls when their results were known.

Example 1 — Fibonacci numbers

Let’s consider fibonacci sequence.

0, 1, 1, 2, 3, 5, 8, …

In mathematical terms, the n-th fibonacci number

F(n) = F(n-1) + F(n-2)

where F(0) = 1 and F(1) = 1.

Therefore, in Python

With memoization trick,

At line 1, a dictionary memo is defined to store and provide quick access to memorized results. At line 6 and 7, we check whether the n-th fibonacci number has already been known or not. If not, the result is computed normally with recursive calls to fibo(n-2) and fibo(n-1) and saved to memo. Otherwise, it returns the saved result right away (line 8).

Of course, we gain some speed.

But our fibo(n) method becomes less straightforward and a little cluttered. Luckily, in Python, we can fix this problem easily with decorators.

Python Decorator

Decorator is a function that modifies(decorates) other functions. It takes function as input and returns a decorated function as output.

Example 2 — Currency decorator

Let say we want to format numbers as currency. Instead of putting formatting line in each of our interest calculator functions, we can define another function, a decorator, to wrap around our interest calculators and reformat their outputs. In other words, with decorators, we can separate presentation logic from main logic resulting a cleaner code.

will give this

$1,150.00
$1,160.54

Implement memoization using decorator

Let’s turn back to our fibonacci example. To enable memoization, what we need are 1) a place to store results from computed n-th fibonacci numbers, and 2) a wrapper function that checks, beforehand, if the result was already known. Belowis how you would put all these requirements into one separated place using decorator.

Then just add a decorator syntax @memoize on top of fibo(n) and it’s done. Memoization ready.

Example 3 — Dragon curve

The dragon curve on the left is the product of the following recursions.

d(n) = d(n-1) + L + b(n-1)
b(n) = d(n-1) + R + b(n-1)
, d(0) = F and b(0) = F.

These recursions generate a sequence of commands that control how the dragon will be drawn. Starting at the origin with current direction heading towards (1, 0),

• F moves a pen one step,
• L changes direction 90° CCW,
• R changes direction 90° CW.

In this example, we have two recursive functions to handle. The memoize() decorator needs to be able to distinguish between d(n) and b(n). However, when a function is wrapped, it loses its __name__ attribute and we kind of need this func.__name__ to identify the function that is being memoized. That is why, at line 7, we need to wrap the wrapper function with functools.wraps to restore all the attributes (including __name__) to the values the wrapped function would have if it was not decorated.

Enjoy Pythoning.