How to optimize this function for Fibonacci sequence?

Question

On the website codility there is an initial challenge for you to refactor this code:

var yourself = {
    fibonacci : function(n) {
        if (n === 0) {
            return 0;
        }
        if (n === 1) {
            return 1;
        }
        else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

And even making changes I end up stuck to the use of recursion, and with that I get the message that the execution is very slow (Correct value, but the Execution takes Too long. Improve it!).

The question is, what are the other ways to do this calculation?

Answer 1

The Fibonacci sequence generates numbers that grow very quickly. It turns out that the way you’re doing, each recursive call will create other recursive calls that create other recursive calls that create other recursive calls... until at the end of each recursive call, a 0 or 1 result is produced.

Here is an example of what happens, with fibonacci(8):

In this table above, the left column represents the first call of fibonacci(8). It reduces to two other calls to fibonacci(7) and the fibonacci(6), that are in the second column. Each of these calls will subdivide several times until at the end we will have a lot of zeros and a.

With this we can form a call tree. In the leaves of these trees we have zeros and ones that will be returned to the calling functions and will be summed up to provide the final result, which is 21.

Note that we have the number 1 appearing on 21 sheets. We also have the number 0 appearing on 13 sheets. 13 is also the result of fibonacci(7). In total there are 34 leaves, which is the result of fibonacci(9).

If you mount this tree with other numbers, you will see that for any number n, the number of sheets shall be fibonacci(n + 1), the number of sheets with 1 shall be fibonacci(n) and the number of sheets with 0 will be fibonacci(n - 1).

Each of these sheets requires a processing to be achieved. And in the end, we can see that we’re actually just adding up the results of a lot of zeros and ones. That’s a pretty large number of sums. In total the sum operation happens fibonacci(n + 1) - 1 times.

Now, let’s take the result of fibonacci(80), which is 23,416,728,348,467,684. This means that your program will take forever to add up a lot of zeros and ones to reach that number. This is why the program is slow. Using the approach demonstrated in reply from Antonio Carlos, this is solved. To calculate fibonacci(n), in fact are only needed (n - 1) sums. That is, to calculate fibonacci(80) we only need 79 sums actually.

If we look at this tree up there, we see that a lot of results are recalculated over and over and over again. Therefore, if we store intermediate results already obtained previously in a table, we can later consult them instead of recalculate them, leaving the program more efficient. This is the principle of dynamic programming. To calculate the fibonacci(n), we have to calculate first the fibonacci(n - 1), until then ok. But when calculating the fibonacci(n - 1), we will also have calculated the fibonacci(n - 2). This way, we don’t need to recalculate the fibonacci(n - 2), if we have saved its result when calculating the fibonacci(n - 1), just add up this saved result, which avoids having to repurchase it.

In the program of reply from Antonio Carlos, it uses only the variables a and b. This is because in fact we only need the two most recent results of the table, because when calculating fibonacci(n), these two oldest results will be the fibonacci(n - 1) and the fibonacci(n - 2). This way, anything after the fibonacci(n - 3) can be forgotten because it will no longer be necessary. Thus, we can keep the table only with the last two results when representing it only with two variables, a and b. The variable f is just an auxiliary variable so that nothing is lost while the table is being changed, which is evidenced if its code is rewritten like this:

var fibonacci = function(n) {
    var a = 0, b = 1;
    for (var i = 2; i <= n; i++) {
        var f = a;
        a = b;
        b += f;
    }
    return b;
};

Answer 2

An easy way to implement such a function efficiently is by using dynamic programming, which basically consists of storing intermediate results that will be reused.

In the case of Fibonacci, simply store the last two results, instead of calculating them at each call. So, we have:

var fibonacci = function(n) {
    var a = 0, b = 1, f = 1;
    for(var i = 2; i <= n; i++) {
        f = a + b;
        a = b;
        b = f;
    }
    return f;
};

Source: The Polyglot Developer

Answer 3

An approach memorizer, directly using the initial algorithm:

var yourself = {
    cache:{},
    fibonacci : function(n) {
        if (n in this.cache){ return this.cache[n] }
        if (n === 0)        { return 0;            }
        if (n === 1)        { return 1;            }
        return this.cache[n]=this.fibonacci(n-1) + this.fibonacci(n-2);
    }
};

yourself.fibonacci(100);