Can someone explain to me how this recursive function works for itself?

Question

taken from this link that I came across trying to figure it out.

Here's the function (modified bit to try to help yourself understand):

(function(){ fibonacci = (function () { var cache = {}; return function (n) { var cached = cache[n]; if (cached) { console.log('already in the ', cache); return cached; } if (n <= 1) { console.log('no 0s or 1s, ', n); return n; } console.log('a brand new ', n, 'consider yourself cached'); cache[n] = fibonacci(n - 2) + fibonacci(n - 1); console.log('current cache: ', cache); return cache[n]; }; }()); fibonacci(20); })(); 

I changed it a bit to try to help myself understand, but I am lost because the output goes to 0, then it increases from 0. I would think that in this statement:

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

fibonacci(n - 2) will be evaluated, then fibonacci(n - 1) right after that.
But even if that were the case, I don’t understand how JavaScript will add these two functions together.

Can someone help me understand how this works, or at least you can help me restructure it in a way that might be a little easier to understand?

Here's the conclusion:

 a brand new 20 consider yourself cached a brand new 18 consider yourself cached a brand new 16 consider yourself cached a brand new 14 consider yourself cached a brand new 12 consider yourself cached a brand new 10 consider yourself cached a brand new 8 consider yourself cached a brand new 6 consider yourself cached a brand new 4 consider yourself cached a brand new 2 consider yourself cached no 0s or 1s, 0 no 0s or 1s, 1 current cache: Object {2: 1} a brand new 3 consider yourself cached no 0s or 1s, 1 already in the Object {2: 1} current cache: Object {2: 1, 3: 2} current cache: Object {2: 1, 3: 2, 4: 3} a brand new 5 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3} already in the Object {2: 1, 3: 2, 4: 3} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} a brand new 7 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} a brand new 9 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} a brand new 11 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} a brand new 13 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} a brand new 15 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} a brand new 17 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} a brand new 19 consider yourself cached already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} already in the Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181} current cache: Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765} 

Thank you, I know that recursion is probably the big question about the Nob, and I used it several times, but understanding how it works makes my head spin.

Answer 1

It may be easier for you if the code is simplified and you start with a smaller number, say 4. Below is the functionality identical to what you originally placed:

 var cache = {}; function fibonacci(n) { // assume n = 4 var cached = cache[n]; 

For the first time, cache [4] will be undefined, so the following test evaluates to false:

  if (cached) { console.log('already in the ', cache); return cached; } 

Like n = 4, the following is also not true:

  if (n <= 1) { console.log('no 0s or 1s, ', n); return n; } 

Then the following lines are executed:

  console.log('a brand new ', n, 'consider yourself cached'); // 4 cache[n] = fibonacci(n - 2) + fibonacci(n - 1); 

which the:

  cache[4] = fibonacci(2) + fibonacci(3); 

The line above evaluates the left side first, initiating the creation of the "4" cache property. Actually this has not been created yet, since the statement is not finished, so you almost have:

 cache = {4:undefined}; 

Then, the right side is evaluated to see what will be assigned. Since there is a + operator, both expressions must be evaluated to see if it is considered as complement or concatenation.

Further, fibonacci(2) is evaluated fibonacci(2) whether there is + addition or concatenation, the evaluation continues from left to right), so the process described above is repeated, creating:

  cache[2] = fibonacci(0) + fibonacci(1); 

and you almost have:

 cache = {4:undefined, 2:undefined}; 

Noting that the properties have not yet been created.

fibonacci(0) is now evaluated. This time it falls into the second if and returns 0, so no cache['0'] is created, and now you have:

 cache[2] = 0 + fibonacci(1); 

Again, when evaluating fibonacci(1) , the second if is executed and returns 1 , so you have a value for the assignment, so that the property and the assigned value are created:

  cache[2] = 0 + 1; // cache = {2:1, 4:undefined}; 

Now go to the next line:

  console.log('current cache: ', cache); return cache[n]; // returns 1; } 

So the previous call continues:

  cache[4] = 1 + fibonacci(3); 

again he gets:

  cache[3] = fibonacci(1) + fibonacci(2); 

The first expression returns 1 from the first if , so you have:

  cache[3] = 1 + fibonacci(2); 

The second expression goes to the first if cache [2] exists, so it returns 1 (that is, the value of cache [2]), and you have:

  cache[3] = 1 + 1; // cache = {3:1, 3:2, 4:undefined}; 

and then returns cache [3] (which is 2) so you return:

  cache[4] = 1 + 2; 

and now there is a cache = {2: 1, 3: 2, 3: 3}

You can write this as a sequential operation (all recursive functions can be written as sequential operations), which is common when speed matters, because sequential operations are always faster. In this case, the sequential function is very simple:

 function fibonacci2(n) { var fibs = {0:0, 1:1}; var i = 1; while (i < n) { fibs[++i] = fibs[i-1] + fibs[i-2]; } return fibs; } console.log(fibonacci2(4)); 

Answer 2

"I do not understand how JavaScript will add these two functions together."

JS does not add functions; it adds the values ​​returned from these function calls. Let's say that f (n-2) was calculated, when called f (n-1), it will be calculated by the formula:

 f(n-1) = f(n-2) + f(n-3) 

and now, since we calculated both values ​​on the right side of the equation, both values ​​will be taken from the cache.

Let us demonstrate this with an example, suppose we want to calculate f (5):

 f(5) = f(4) + f(3) 

recursive call with f (3):

 f(3) = f(2) + f(1) 

recursive call:

 f(1) = 1 and f(2) = cached(f(1)) + f(0) = 1 + 0 = 1 

now we return to calc f (3), and both f (2) and f (1) are cached, therefore:

 f(3) = 1 + 1 = 2 

returns to calc f (4)

 f(4) = f(3) + f(2) = 2 + 1 = 3 

finish again:

 f(5) = f(4) + f(3) = 3 + 2 = 5 

Note that once you reach the deepest recursion point (f (1)), the entire cache backup path will be used, and none of the values ​​will be calculated, which makes this implementation very efficient!