4

取自此链接，我在尝试解决此问题时遇到了该链接。

这是功能（稍作修改以尝试帮助自己理解）：

(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}

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

4

2 回答 2

3

“我不明白 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

现在我们回到 calc 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）），将使用一路备份的缓存并且不会计算任何值，这使得这个实现非常高效！

于 2013-04-23T05:16:23.783 回答
1

如果简化代码并从较小的数字（例如 4）开始，您可能会发现更容易。以下功能与您最初发布的功能相同：

var cache = {};

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

第一次通过时，cache[4] 将是未定义的，因此以下测试评估为 false：

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

由于 n = 4，以下也是错误的：

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

然后执行以下行：

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

这是：

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

在上面的行中，首先评估左侧，开始创建 '4' 属性cache。它实际上还没有创建，因为语句还没有完成，所以你几乎有：

cache = {4:undefined};

然后评估右侧以查看将分配的内容。由于存在+运算符，因此必须评估两个表达式以查看它是被视为加法还是连接。

接下来fibonacci(2)是求值（无论+是加法还是串联，求值从左到右进行），所以重复上述过程，创建：

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

你几乎有：

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

注意到这些属性实际上还没有创建。

现在fibonacci(0)进行评估。这次它到达第二个if并返回 0，所以没有cache['0']创建，现在你有：

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

同样，在评估fibonacci(1)第二if条语句时执行并返回1，因此您有一个要分配的值，因此创建了一个属性并分配了值：

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

现在进入下一行：

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

所以现在之前的调用继续：

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

它再次到达：

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

第一个表达式1从第一个返回，if所以你有：

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

第二个表达式到达第一个 if，其中 cache[2] 存在，所以它返回 1（即 cache[2] 的值），你有：

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

然后返回 cache[3] （即 2），这样你就回到了：

    cache[4] = 1 + 2;

现在有 cache = {2:1, 3:2, 3:3}

您可以将上述内容编写为顺序操作（所有递归函数都可以编写为顺序操作），这在速度很重要的情况下很常见，因为顺序操作总是更快。在这种情况下，顺序函数非常简单：

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));
于 2013-04-23T23:05:42.023 回答