Javascript Memoization Explanation?

Question

Reading an example from a book, can someone explain how the function call to fibonacci takes in the argument 'i' when the function itself doesn't declare any parameters?

var fibonacci = (function () {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}());

for(var i = 0; i <= 10; i += 1) {
    document.writeln('// ' + i + ': ' + fibonacci(i));
}

Answer 1

You are creating a self-executing anonymous function (function(){}()); which inside it returns the fib function, which takes an argument. var fib = function(n){} ... return fib;

var fibonacci = (function () { // Self-executing anonymous function
    var memo = [0, 1];         // local variable within anonymous function
    var fib = function (n) {   // actual fib function (takes one argument)
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
    return fib; // return fib (fibonacci is now set to the function fib defined above, which takes one argument)
}());

This system (returning a function from a self-executing anonymous function) allows for you to define variable in a local scope that can still be used by the returned function, but not by functions outside the scope. Here is an example.

This technique is called closure in JavaScript. Read more about it on the MDN guide.

Answer 2

To understand this, I think it is helpful to work with a simpler example. Take a look at the two memoized functions below. The only difference is the () after add : function (){ ... }() on the successful memorization code.

    var failed_memoization = {
        add : function (){
            var counter;
            return function(number){
                if(counter){
                    counter = counter + number;
                    return counter;
                }
                counter = number;
                return counter;
            } //NOTE: NO function call brackets here
        }
    }

    var successful_memoization = {
        add : function (){
            var counter;
            return function(number){
                if(counter){
                    counter = counter + number;
                    return counter;
                }
                counter = number;
                return counter;
            }
        }()  //NOTE: the function call brackets here!!
    };
}

Now let's execute these two functions.

console.log('Failed Memoization');
console.log(failed_memoization.add(5));      //We wanted 5, but this prints the text of the function instead.... Okay, lets try something else
console.log(failed_memoization.add()(5));    //5
console.log(failed_memoization.add()(10));   //10 (Wanted it to be 5+10 = 15.
console.log('successful_memoization');
console.log(successful_memoization.add(8));  //8
console.log(successful_memoization.add(16)); //24 (This is what we wanted 8 + 16 = 24)

So what's going on here is that for successful_memoization when we put () to the end of its add : function(){...}(). As such, this function is executed immediately on the creation of the static object. In turn, executing that function returns the object function (number){...} wich results in the assignment: add : function (number){...} NOT add : function(){} as it initially appears.

What is also important to note is that var counter is declared outside return function(name){}. As it is still being used within add : function(number){...}, this variable is accessible within that function. For failed_memoization.add()(number), it uses a new counter each time we execute that function, because we execute the first function, and then the inner function on each call. For successful_memoization.add(number) we executed the outer function upon initialization, and so counter will persist through all subsequent calls and will not be overwritten.

Answer 3

Because the function returns a function that does take a parameter.

Answer 4

There is a self-calling function that returns the function with the identifier fib which is then assigned to the identifier fibonacci. This way you can create a private variable memo which is only accessible by the function. So var fibonacci in fact is function(n){...}.

Answer 5

var fibonacci = (function() {
    ...
    return fib;
})();

This is a self-executing function.

It declares a function expression which returns a function (fib), executes the outer function expression immediately (()), and assigns its return value (which is fib) to the fibonacci variable.

Answer 6

Function fibonacci does take one argument. Note that the unnamed function that starts on the first line is not the function that ends up being known as fibonacci. That unnamed function is immediately called since you have () immediately after closing brace }. This unnamed function returns fib, a local variable to which a single-argument function is assigned. Thus, fibonacci ends up referring to the function returned by the unnamed function, i.e. fibonacci is this:

var fib = function (n) {
    var result = memo[n];
    if (typeof result !== 'number') {
        result = fib(n - 1) + fib(n - 2);
        memo[n] = result;
    }
    return result;
};

Note that this function refers to local variables of the unnamed function for the purpose of memoizing.

The critical thing to notice was () which calls the unnamed function immediately, here are some examples that illustrate this technique:

var a = (function() { return 1; });

Variable a holds a function which returns 1.

var a = (function() { return 1; }());

Here however, variable a holds value 1.