javascript - 有人可以向我解释如何将这个递归函数添加到自身吗？

Question

取自此link ，这是我在尝试解决这个问题时遇到的。

函数如下(稍作修改以帮助自己理解):

(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);

})();

我稍微修改了一下，试图帮助自己理解，但我迷路了，因为输出趋向于 0，然后从 0 增加。我本以为在这个语句中:

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

fibonacci(n - 2) 将被计算，然后是 fibonacci(n - 1)。
但即使是这样，我也不明白 JavaScript 是如何将这两个函数加在一起的。

谁能帮助我稍微了解一下它的工作原理，或者至少，您能帮我以一种更容易理解的方式重组它吗？

这是输出:

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} 

谢谢，我知道递归可能是一个大菜鸟问题，我已经用过几次，但了解它的工作原理让我头晕目眩。

Answer 1

“我不明白 JavaScript 如何将这两个功能加在一起。”

JS 不添加函数，它添加从这些函数调用返回的值。假设计算了 f(n-2)，当调用 f(n-1) 时，它将通过以下方式计算:

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

现在，由于我们在等式右侧计算了两个值，因此两个值都将从缓存中获取。

举个例子，假设我们要计算f(5):

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

使用 f(3) 的递归调用:

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

递归调用:

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

现在我们回到计算 f(3) 并且我们缓存了值 f(2) 和 f(1)，因此:

f(3) = 1 + 1 = 2

回到计算 f(4)

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

再次结束:

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

请注意，一旦到达递归的最深点 (f(1))，将使用所有备份缓存并且不会计算任何值，这使得此实现非常高效!