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,theleftcolumnrepresentsthefirstcallof`fibonacci(8)`

.Itisreducedtotwoothercallsto`fibonacci(7)`

and`fibonacci(6)`

,whichareinthesecondcolumn.Eachofthesecallswillbesubdividedseveraltimesuntilattheendwewillhavealotofzerosandones.

Withthiswecanformacalltree.Intheleavesofthesetreeswehavezerosandonesthatwillbereturnedtothecallingfunctionsandwillbesummeduptoprovidethefinalresult,whichis21.

Noticethatwehavethenumber1appearingon21sheets.Wealsohavethenumber0appearingon13sheets.13isalsotheresultof`fibonacci(7)`

.Intotalthereare34sheets,whichistheresultof`fibonacci(9)`

.

Ifyoumountthistreewithothernumbers,youwillseethatforanynumber`n`

,thenumberofsheetswillbe`fibonacci(n+1)`

,thenumberofsheetswith1willbe`fibonacci(n)`

andthenumberofsheetswith0willbe`fibonacci(n-1)`

.

Eachofthesesheetsrequiresprocessingtobeachieved.Andintheend,wecanseethatwe'reactuallyjustsumminguptheresultsofabunchofzerosandones.Thatisaverylargenumberofsums.Intotalthesumoperationhappens`fibonacci(n+1)-1`

times.

Now,let'staketheresultof`fibonacci(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;
};
```