# Memoization and Decorators with Python

Recursion offers programmers a convenient way to break larger problems into manageable pieces. Consider the iterative versus recursive solutions for a fibonacci sum.

# iterative

def fib_iterative(n):

if (n == 0):

return 0

elif (n == 1):

return 1

elif (n >1 ):

fn = 0

fn1 = 1

fn2 = 2

for i in range(3, n):

fn = fn1+fn2

fn1 = fn2

fn2 = fn

return fn# recursive

def fib(n):

if n == 0:return 0

if n == 1:return 1

else: return fib(n-1) + fib(n-2)

Recursive solutions are often easier to read and write for branching problems. Tree traversals, graph traversals, and mathematical series are (often) dealt with more intuitively using recursion.

Though it affords convenience, the computational time cost of recursion on branching problems grows exponentially with larger values of n.

Lets take a look at the call stack for fib(6)

We do roughly twice as many operations at each successive level of the tree. Giving us a time complexity O(2^n).

If we take a closer look at our tree, you’ll notice that we’re repeating work. fib(2) is calculated five times, fib(3) is calculated three times and so on. Though this isn’t a problem for small values of *n*,* *imagine the amount of repeated work in calculating fib(1000).** Once we revise our recursive solution, try running the same problem (say fib of 20) for both versions and notice the remarkable difference in the time to completion.**

Surely there’s a good way to prevent repeated work, and keep our elegant solution?

# Memoization: You can have your Cake and Eat it Too!

With memoization, we can “memoize” (remember, store) the result of problems that we’ve dealt with before, and return a stored result instead of repeating calculations.

For example, once fib(2) is calculated, we can store the result and use it the next four times fib(2) is encountered.

This reduces our run-time from O(2^n) to O(n) because we’re calculating each of fib(0)…fib(n) only once.

One way to accomplish this is using a dictionary.

__fib_cache = {}def fib_memo(n):

if n in __fib_cache:

return __fib_cache[n]

else:

__fib_cache[n] = n if n < 2 else fib_memo(n-2) + fib_memo(n-1)

return __fib_cache[n]

And voila! We’ve successfully memoized a recursive function!

However we can take things one step further and abstract memoization for any recursive function!

# Decorators : Functions using functions to perform other Functions

Decorators are known as “Higher order functions” : functions that take other functions as parameters. Here we will use a decorator to generalize memoization.

Here is a decorated solution:

def memoize(func):

cache = func.cache = {} @functools.wraps(func)

def memoized_func(*args, **kwargs):

key = str(args) + str(kwargs)

if key not in cache:

cache[key] = func(*args, **kwargs)

return cache[key] return memoized_func@memoize

def fibonacci(n):

if n == 0:return 0

if n == 1:return 1

else: return fib(n-1) + fib(n-2)

Lets break it down line by line.

Our decorator is a function that takes another function as an argument, we declare it as such on line 1.

Next we declare a dictionary `func.cache = {}`

, which is declared as a property of`func`

. Here we will store each unique call made by `func.`

We’ll come back to `@functools.wraps`

.

`def memoized_func(*args, **kwargs):`

— Inside the decorator we define a new, memoized function based on the `func`

we passed in, and it takes in the same parameters are `func`

. We call this new version `memoized_func`

.

`*args`

is a keyword indicating that `memoizer`

takes an arbitrary number of arguments e.g.`def memoize(one two three)`

or `def memoize(just_one)`

are both valid. Similarly `*kwargs`

represents an arbitrary number of keyword arguments (parameters defined at the function call) e.g. `def memoize(one = 1, two = 2, three = 3)`

. Note : You can use these specialized parameters in any function.

The following line declares a `key`

for our `func.cache`

based on the parameters given. If we have seen this combination of parameters before, we pull the result from `func.cache`

, otherwise create a new key using the original `func`

as it was defined (e.g. using `fib`

), and assign it’s value to the result e.g. ( store the result of `fib(2)`

).

The last line inside `memoized_func()`

returns the result of a single call to `func`

with the given parameters.

The final line returns `memoized_func()`

, which represents a modified version of our original function with added (decorated) features, that is, storing the result of each new call.

Finally we mark our original function with `@memoize`

. The ‘@’ notation tells the compiler to pass the function immediately below it into a higher order function called `memoized_func`

— which in our case returns a memoized version of `fibonacci()`

. This version of the function will immediately return results we’ve calculated before, otherwise it will call the original `fib()`

function to determine what that number should be.

# What is @functools.wraps?

`@functools.wraps`

is yet another decorator that is built into python. It allows decorator`memoize`

to store information related the memorized function’s docstring, or function name so that information can be accessed later. If we were to ask python `fib.__name__`

or `fib.__doc__`

(these are built in properties to functions), without `@functools.wraps`

we it would return the name and docstring for `memoized_fib`

and not `fib`

itself. For debugging purposes, it’s helpful to have access to the name and docstring of the original function being called, not the decorating function, as the same decorator could be applied to a multitude of functions.

# Try it yourself!

Next time you come across a recursive function, think about whether you can improve its performance with memoization, and then abstract that memoization to other functions by adding a decorator!