How to optimize this function for Fibonacci sequence?

The Fibonacci sequence generates numbers that grow very quickly. It happens that the way you are 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 result of 0 or 1 is produced. >

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

Inthistableabove,theleftcolumnrepresentsthefirstcalloffibonacci(8).Itisreducedtotwoothercallstofibonacci(7)andfibonacci(6),whichareinthesecondcolumn.Eachofthesecallswillbesubdividedseveraltimesuntilattheendwewillhavealotofzerosandones.

Withthiswecanformacalltree.Intheleavesofthesetreeswehavezerosandonesthatwillbereturnedtothecallingfunctionsandwillbesummeduptoprovidethefinalresult,whichis21.

Noticethatwehavethenumber1appearingon21sheets.Wealsohavethenumber0appearingon13sheets.13isalsotheresultoffibonacci(7).Intotalthereare34sheets,whichistheresultoffibonacci(9).

Ifyoumountthistreewithothernumbers,youwillseethatforanynumbern,thenumberofsheetswillbefibonacci(n+1),thenumberofsheetswith1willbefibonacci(n)andthenumberofsheetswith0willbefibonacci(n-1).

Eachofthesesheetsrequiresprocessingtobeachieved.Andintheend,wecanseethatwe'reactuallyjustsumminguptheresultsofabunchofzerosandones.Thatisaverylargenumberofsums.Intotalthesumoperationhappensfibonacci(n+1)-1times.

Now,let'staketheresultoffibonacci(80),whichis23,416,728,348,467,684.Thatmeansyourprogramwilltakeforevertogetridofzerosandonesuntilyougettothatnumber.That'swhytheprogramisslow.Usingtheapproachshownin Antonio Carlos's answer , this is fixed. To calculate fibonacci(n) , in fact only only (n - 1) sum is required. That is, to calculate fibonacci(80) we only need 79 sums in fact.

If we look at this tree up there, we will see that a lot of results are recalculated over and 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 recalculating them, leaving the program more efficient. This is the principle of dynamic programming. To calculate fibonacci(n) , we have to first calculate fibonacci(n - 1) , until then ok. But when calculating fibonacci(n - 1) , we have already calculated fibonacci(n - 2) . Thus, we do not need to recalculate fibonacci(n - 2) , if we have saved the result of it when calculating fibonacci(n - 1) , simply add this result already saved, which avoids having to recompute it.

In the Antonio Carlos answer program, it uses only the variables a and b . This is because we actually only need the two most recent results from the table, because when calculating fibonacci(n) , these two oldest results will be fibonacci(n - 1) and fibonacci(n - 2) . In this way anything after fibonacci(n - 3) can be forgotten because it will no longer be necessary. Thus, we can keep the table with only the last two results by representing it with only two variables, a and b . The variable f is just an auxiliary variable so that nothing is lost while the table is being changed, a fact that 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;
};

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

In the case of Fibonacci, just store the last two results, instead of calculating them with 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

A memory approach , 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);