### Introduction

In Part 1 of this series we looked at a simple function generator for memoizing functions. Recall memoized functions are functions that cache their results; once the value is determined for a particular input the value is placed into a cache and subsequent calls to the function using the same input return the previously cached value — thus *eliding* the function call. Using a fibonacci sequence generator we examined how memoized functions can greatly improve program performance.

### Memoizing Recursive Functions

Let’s take another look at the Fibonacci function presented in the previous post:

// retrieve nth fibonacci number from sequence (0-relative) // recursive solution for fibonacci calculation is not efficient function fibonacci(idx) { if (idx == 0) return 0; if (idx == 1) return 1; return fibonacci(idx-2) + fibonacci(idx-1); }

What’s the problem here? Let’s suppose we’ve generated a memoized version of this fibonacci function, called *mfibonacci*, and we call *mfibonacci(10)*. What’s happening? At a high level we’re going to return

*fibonacci(8) + fibonacci(9)*

Do you see the problem? We’re not calling memoized versions of our fibonacci function in our recursive generation! In calculating *mfibonacci(10)* we’ve calculated *fibonacci(9), fibonacci(8), fibonacci(7), fibonacci(6), fibonacci(5), fibonacci(4), fibonacci(3), fibonacci(2)* and none of these values have been cached. If after calling *mfibonacci(10)* we were to subsequently call *mfibonacci(9)*, we’d have to start all over again. The fact we’ve already calculated *fibonacci(9)* while computing *mfibonacci(10)* has been lost.

This particular implementation of *fibonacci* compounds the problem:

*fibonacci(n) = fibonacci(n-2) + fibonacci(n-1)*

When calling *mfibonacci(10)* both *fibonacci(8)* and *fibonacci(9)* are called. We’d like the result of *fibonacci(8)* to be cached and available when calling *fibonacci(9)*. This implementation of *fibonacci* was deliberately chosen for this pathological case.

How do we memoize recursive functions?

### Re-Thinking Memoize

We need to backtrack a little bit. Previously we used the following function generator for memoizing functions:

// Return a memoizing version of a function f function memoize(f) { if (f instanceof Function) { // only memoize functions of arity 1, otherwise return function if (f.length == 0 || f.length > 1) return f; var fn = function(x) { if (fn.memoizer.values[x] == null) { fn.memoizer.values[x] = f.call(f,x); } return fn.memoizer.values[x]; }; fn.memoizer = { values : [] }; return fn; } else { return f; // garbage in, garbage out I always say! } }

While this function generator works, it’s less than ideal. To see what’s wrong consider the following contrived scenario:

memoize(fibonacci)(10); memoize(fibonacci)(10);

Here the function generator *memoize* is creating a new and separate memoized version of *fibonacci* — each having their own cache! That’s not what we want. Instead we’d like the function’s memoization to be a property of the function itself. This way everyone getting the memoized form of a function are getting the same implementation, and more importantly, the same cached set of values.

It’s extremely useful to make a function’s memoized form a property of the function itself. In JavaScript functions are first-order objects: they can be assigned to variables, stored in properties, passed as function arguments and so forth. There are many ways you can get a reference to a function and it would be convenient to get the memoized form of the function in a uniform way.

How do we do that?

### Function Prototype

The solution is to place the memoizer function and the property to the memoized form of the function in the function prototype. Recall that in JavaScript whatever functions and properties exist in the object’s prototype also exist in all instances of the object. You may also recall that in JavaScript all functions are objects — all being instances of the base *Function* object. Whatever methods and properties we add to *Function.prototype* will therefore exist for all functions.

We don’t typically think of functions as being objects having methods and properties, but in JavaScript that’s exactly what they are. Now let’s look at how we can add a memoizer and memoized form property to a *Function.prototype*:

// Return a memoizing version of function Function.prototype.memoize = function() { // only memoize functions of arity 1, otherwise return function if (this.length == 0 || this.length > 1) return this; var _this = this, _caller = this.caller; if (this.memoizer == null) { this.memoizer = { fn : function(x) { if (_this.memoizer.values[x] == null) { _this.memoizer.values[x] = _this.call(_caller, x); } return _this.memoizer.values[x]; }, values: [] } } return this.memoizer.fn.wrap(this); }

As before we only memoize functions whose arity is 1. *this* refers to the function object being memoized. We’re adding a new *memoizer* property to the function. The *memoizer* property is an object having 2 properties:

The memoized form of this function*fn*The value cache for the memoized form of this function*values*

The key difference now is *memoize* is a property of the function instance. Meaning regardless of how many times we call *memoize* we’re retrieving the same memoized form for the function.

Once we’ve gotten over the fact that functions are objects and may therefore have their own properties and methods, we need to be careful to delegate those properties in the memoized form of the function. That’s what *wrap* does:

// Wrap an object, pulling wrapped object properties up to wrapper // so as to make them accessible Object.prototype.wrap = function(o) { for (var p in o) { if (o.hasOwnProperty(p)) { this[p] = o[p]; } } return this; }

We won’t discuss the *wrap* function any further at this time. We’ll see the importance of *wrap* in future posts.

### Memoizing Fibonacci

Let’s put this all together and generate a fully memoized form of *fibonacci*:

// retrieve nth fibonacci number from sequence (0-relative) // memoized solution for fibonacci calculation is very efficient function fibonacci(idx) { if (fibonacci.memoizer == null || !fibonacci.memoizer._fibonacci) { var innerFibonacci = function(idx) { if (idx == 0) return 0; if (idx == 1) return 1; return innerFibonacci(idx-2) + innerFibonacci(idx-1); }.memoize(); fibonacci.memoizer = innerFibonacci.memoizer; fibonacci.memoizer._fibonacci = true; } return fibonacci.memoizer.fn(idx); }

The *innerFibonacci* is key to the implementation. It’s a function object assigned to a memoized form of an anonymous function implementation of the fibonacci function. The *innerFibonacci* references within the anonymous function definition refer to this outer *innerFibonacci* variable being defined. Thus the recursive form is fully memoized.

The second key to this implementation is aliasing the *innerFibonacci* memoizer with the *fibonacci* memoizer. It’s our *Function.prototype* version of *memoize* that allows us to do this: it created the *memoizer* property on the function that we can now refer to. When we retrieve the *Fibonacci* memoizer we’ll actually be retrieving the *innerFibonacci* memoizer — which is exactly what we want.

Finally, notice how we nonchalantly call the *memoize* method on the anonymous fibonacci function we’ve created at runtime. Now you should begin to understand that in JavaScript functions are objects and as such may have properties and methods and that these properties and methods not only apply to named functions but anonymous functions as well.

### What’s Next

We’ve seen how to create fully memoized forms of recursive functions. In so doing we’ve created a single value cache for a function’s memoized form. Both are vast improvements to where we were at the end of the previous post when we first considered memoization.

We’re still not done with memoization however. We’ve not looked at any aspect of cache management. Currently our memoization cache will grow without bounds. We may need to limit both the size constraints and time constraints of the cache. We may only wish to cache so many values based off frequency of use. We may be dealing with a function that returns different values over time even when provided with the same inputs, meaning we may need to empty the cache when some time limit has been exceeded.

In future posts we’ll look at ways of enhancing our *memoize* implementation to provide these capabilities. See you then!

#### More to Explore

Functional JavaScript — Memoization, Part I

Functional JavaScript — Tail Call Optimization and Trampolines

Functional JavaScript — Currying

Pingback: Memoized Fibonacci Sequence in LISP | mtaylorprogramming