Why does this memoization implementation work on a

2019-02-19 12:40发布

问题:

I'm trying to use memoization to optimize an explicitly self recursive implementation of the Fibonacci function. The implementation which is fairly standard (a simple and rather naïve implementation though to focus on the actual problem) follows.

Function.prototype.memoize = function () {
    var originalFunction = this,
        slice = Array.prototype.slice;
        cache = {};
    return function () {
        var key = slice.call(arguments);
        if (key in cache) {
            return cache[key];
        } else {
            return cache[key] = originalFunction.apply(this, key);
        }
    };
};

Now, when creating and memoizing a function as follows, this works1. (Scenario 1)

var fibonacci = function (n) {
    return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}.memoize();

console.log(fibonacci(100));

However, the following does not.2 (Scenario 2)

var fibonacci = function (n) {
    return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

console.log(fibonacci.memoize()(100));

And neither does this.2 (Scenario 3)

function fibonacci(n) {
    return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci.memoize()(100));

My assumption is that because of the different ways of calling memoize() on the functions, something is changing. Note that the functions are otherwise identical. I suppose that this could be due to the fact that other than in the first instance, only the first call is memoized, not the recursive calls.

Question

If my supposition above is indeed correct, then why is this happening? Can someone explain in detail how the latter two scenarios differ from the first?

1To work in this instance means to return the 100th Fibonacci number since it is only possible to compute it recursively if memoization is used.

2To not work is to crash the browser.

回答1:

Yes, it's right that only the first call is memoized in the second and third scenarios.

In the first scenario the reference to the original function only exists as a value, then memoize is applied to that and the fibonacci variable contains the reference to the memoized function.

In the second and third scenario fibonacci is a reference to the original function. The value of the expression fibonaci.memoize() that contains the reference to the memoized function only exist as a value before it is called once.

The memoize method doesn't change the original function, instead it returns a new function that wraps the original function. The original function is unchanged, and to use the memoization you have to call the function returned by the memoize method.

In the first scenario when the function makes a recursive call to fibonacci, it's the memoized function that is used. In the second and third scenarios when the recursive call is made, fibonacci is the original function instead.