caching - JavaScript Fibonacci breakdown

Question

I hope it is ok that I am posting this question here even though I have also posted it on other sites. If I have failed to follow proper protocols, I apologize and please let me know right away so I may remove the post and learn my lessons.

I've been a front end developer for over a year now. I went to school to learn web development, and I consider myself a somewhat capable coder when it comes to simple JavaScript stuff. But when it comes to writing any type of Fibonacci function I cannot do it. It is as if I have a piece missing from my brain that would understand how to deal with this simple sequence of numbers. Here is a piece of a working code that I'm pretty sure I got from a John Resig book or somewhere online:

fibonacci = (function () {
    var cache = {};
    return function (n) {

        var cached = cache[n];
        if (cached) return cached;

        if (n <= 1) return n;
        console.log(n);

        return (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
    };
}());

When I call this function with 10 as the argument, I get this sequence: 10,8,6,4,2,3,5,7,9

Here's what I understand:

fibonnaci is assigned an immediately invoked function expression (or self executing blah blah blah), to which a cache is initiated with whatever argument was passed. If the argument was already in the cache, we just return it and live our lives in everlasting peace. If the argument is 1 or less, that is also the end of the function, everlasting peace ensues once more. But if neither of these conditions exist, then the function returns this statement that makes me feel as if I am just a monkey in a human suit.

What I'd like to do is generate the first 10 fibonnaci numbers in the correct sequence, because if I can do that, then I'll feel like I at least understand it.

So when the first two conditions fail, the code creates a new cache variable and sets it equal to the result of the fibonacci function with whatever argument was passed minus 2, and then it adds the result minus 1.... now for my questions

• Question 1: How does the function know what fibonacci(n-2) is if fibonacci(n) has never been computed?
• Question 2: Are recursive functions linear, or what order do they follow?
• Question 3: If I can't understand this, do I have any hope of becoming a programmer?

Thank you for your time.

After getting past this block, I changed the function a bit to see if I could hold on to the result in a variable and output it, just to see what happens, and I got some really unexpected results.

Here's the change:

fibonacci = (function () {
        var cache = {};
        return function (n) {

            var cached = cache[n];
            if (cached) {
                console.log(cached);
                return cached;
            }

            if (n <= 1) {
                console.log(n);
                return n;
            }
            console.log(n);

            var result = (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
            console.log(result);
            return result;
        };
    }());

Here's the resulting pattern: 10,8,6,4,2,0,1,1,3,1,1,2,3,5,2,3,5,8,7,5,8,13,21,9,13,21,34,55 Any help with why this happens?

Answer 1

Well, let's start with what you understand (or say you understand):

fibonnaci is assigned an immediately invoked function expression (or self executing blah blah blah), to which a cache is initiated with whatever argument was passed.

Not quite: fibonnaci is assigned the return value of an IIFE. There's a difference. Inside the IIFE, we se a return function(n) statement. The IIFE is, as it's name suggests, invoked immediatly. the function is created, executed and, once returned, is not being referenced (explicitly) anywhere. The function is returned, is assigned to the variable fibonacci.
This IIFE does create an object literal, called cache. This object resides in the scope of the IIFE, but because of JS's scope scanning(this answer links to others... all of them together explain how JS resolves names to their values), this object is still accessible to the returned function, now assigned to fibonaci.

If the argument was already in the cache, we just return it and live our lives in everlasting peace. If the argument is 1 or less, that is also the end of the function, everlasting peace ensues once more. But [...]

Well, now cache is not created over and over again on each function call (the IIFE is only called once, and that's where cache is created). If the returned function (fibonnaci) changes it, that change to the object will persist in memory. Closure vars, for that is what cache is can be used to hold state between function calls. All the other things you say (n <= 1) is standard recursive function stuff... it's the condition that prevents infinite recursion.

But if neither of these conditions exist, then the function returns this statement that makes me feel as if I am just a monkey in a human suit.

Well, this is actually the fun part. This is where the actual magic happens.
As I've explained, fibonnaci does not reference the IIFE, but rather, it references teh returned function:

function(n)
{
    var cached = cache[n];
    if (cached)
    {
        return cached;
    }
    if (n <= 1)
    {
        return n;
    }
    return (cache[n] = (fibonacci(n-2) + fibonnaci(n-1)));
}

This means, that every occurance of fibonacci can be replaced with the function body. When calling fibonnaci(10), the last (return) statement should be read as:

return (cahce[n] = fibonacci(8) + fibonnaci(9));

Now, as yousee, fibonacci(8) and fibonnaci(9) are called, in the return value. These expression can be written in full, too:

return (cache[10] = (fibonnaci(6) + fibonacci(7)) + (fibonacci(7) + fibonacci(8)));
//which is, actually:
return (cache[10 = ( retrun (cache[6] = fibonacci(4) + fibonacci(5))
                   //since fibonacci(6) cached both fibonacci(5) & fibonacci(6)
                     + return (cache[7] = cache[5] + cache[6])
           + return cache[7] + return (cache[8] = cache[6] + cache[7]

That's how this cache function actually ties in...

We can repeat this until we call fibonnacci(1) or fibonacci(0), because in that case n<=1, and will be returned without any more recursive calls.
Also note that, in writing fibonnaci(9) in full, this actually breaks down into fibonacci(7) + fibonacci(8), both these calls have been made before, and that's why there results were cached. If you don't cache the results of each call, you'll waste time calculating the same thing twice...

BTW: this code is very much "condesed", and works because the specs say that an assignment expression (cache[n] = ...) evaluates to the assigned value, you're returning cache[n], essentially.