JavaScript 斐波那契分解

Question

我希望我在这里发布这个问题是可以的，即使我也将它发布在其他网站上。如果我没有遵守适当的规程，我深表歉意，请立即通知我，以便我删除帖子并吸取教训。

我从事前端开发已经一年多了。我去学校学习网络开发，我认为自己在简单的 JavaScript 方面是一个有点能力的编码员。 但是当谈到编写任何类型的斐波那契函数时，我都做不到。就好像我的大脑中缺少一 block 可以理解如何处理这个简单的数字序列的部分。 这是一段工作代码，我很确定我是从 John Resig 的书或网上的某个地方得到的:

fibonacci = (function () {
    var cache = {};
    return function (n) {

        var cached = cache[n];
        if (cached) return cached;

        if (n <= 1) return n;
        console.log(n);

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

当我以 10 作为参数调用这个函数时，我得到这个序列:10,8,6,4,2,3,5,7,9

这是我的理解:

fibonnaci 被分配了一个立即调用的函数表达式(或自执行等等等等)，无论传递什么参数都会启动缓存。 如果参数已经在缓存中，我们只需返回它并在永恒的和平中过我们的生活。 如果参数为 1 或更小，这也是函数的结束，再次出现永久和平。 但是，如果这两个条件都不存在，那么该函数将返回这样的语句，让我觉得自己好像只是一只穿着人类西装的猴子。

我想做的是以正确的顺序生成前 10 个斐波纳契数，因为如果我能做到这一点，那么我会觉得我至少理解了它。

所以当前两个条件失败时，代码创建一个新的缓存变量并将其设置为等于斐波那契函数的结果，无论传递的参数是负 2，然后它添加结果负 1.... 现在对于我的问题

• 问题 1:如果从未计算过 fibonacci(n)，函数如何知道 fibonacci(n-2) 是多少？
• 问题 2:递归函数是线性的，还是它们遵循什么顺序？
• 问题3:如果我连这个都看不懂，我还有希望成为一名程序员吗？

感谢您的宝贵时间。

通过这个 block 后，我稍微更改了函数，看看是否可以将结果保留在变量中并输出它，只是为了看看会发生什么，我得到了一些非常意想不到的结果。

这里是变化:

fibonacci = (function () {
        var cache = {};
        return function (n) {

            var cached = cache[n];
            if (cached) {
                console.log(cached);
                return cached;
            }

            if (n <= 1) {
                console.log(n);
                return n;
            }
            console.log(n);

            var result = (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
            console.log(result);
            return result;
        };
    }());

这是生成的模式: 10,8,6,4,2,0,1,1,3,1,1,2,3,5,2,3,5,8,7,5,8,13,21,9,13, 21,34,55 对为什么会发生这种情况有帮助吗？

Answer 1

好吧，让我们从你理解(或者说你理解)开始:

fibonnaci is assigned an immediately invoked function expression (or self executing blah blah blah), to which a cache is initiated with whatever argument was passed.

不完全是:fibonnaci 被分配IIFE 的返回值。这是有区别的。在 IIFE 中，我们看到一个 return function(n)陈述。顾名思义，IIFE 立即 被调用。该函数被创建、执行，并且一旦返回，就不会在任何地方(明确地)被引用。函数返回，赋值给变量fibonacci .
这个 IIFE 确实创建了一个对象字面量，叫做 cache .这个对象驻留在 IIFE 的范围内，但是 because of JS's scope scanning (这个答案链接到其他人......所有这些都一起解释了 JS 如何将名称解析为它们的值)，这个对象仍然可以被返回的函数访问，现在分配给斐波那契。

If the argument was already in the cache, we just return it and live our lives in everlasting peace. If the argument is 1 or less, that is also the end of the function, everlasting peace ensues once more. But [...]

那么，现在 cache不会在每次函数调用时一遍又一遍地创建(IIFE 只调用一次，这就是创建 cache 的地方)。如果返回的函数 (fibonnaci) 更改了它，则对对象的更改将保留在内存中。闭包变量，因为这就是 cache is 可用于保存函数调用之间的状态。你说的所有其他事情 ( n <= 1 ) 都是标准递归函数的东西……这是防止无限递归的条件。

But if neither of these conditions exist, then the function returns this statement that makes me feel as if I am just a monkey in a human suit.

嗯，这实际上是有趣的部分。这就是真正的魔法发生的地方。
正如我所解释的，fibonnaci不引用 IIFE，而是引用返回的函数:

function(n)
{
    var cached = cache[n];
    if (cached)
    {
        return cached;
    }
    if (n <= 1)
    {
        return n;
    }
    return (cache[n] = (fibonacci(n-2) + fibonnaci(n-1)));
}

这意味着，fibonacci 的每一次出现可以用函数体替换。调用fibonnaci(10)时，最后一个(返回)语句应该读作:

return (cahce[n] = 斐波那契数 (8) + 斐波那契数 (9));

现在，如您所见，fibonacci(8)和 fibonnaci(9)在返回值中被调用。这些表达式也可以完整地写成:

return (cache[10] = (fibonnaci(6) + fibonacci(7)) + (fibonacci(7) + fibonacci(8)));
//which is, actually:
return (cache[10 = ( retrun (cache[6] = fibonacci(4) + fibonacci(5))
                   //since fibonacci(6) cached both fibonacci(5) & fibonacci(6)
                     + return (cache[7] = cache[5] + cache[6])
           + return cache[7] + return (cache[8] = cache[6] + cache[7]

这就是这个缓存函数实际上与......相关的方式

我们可以重复这个直到我们调用 fibonnacci(1)或 fibonacci(0) ，因为在那种情况下 n<=1 , 并且将在没有任何更多递归调用的情况下返回。
另请注意，写fibonnaci(9)完整地，这实际上分解为 fibonacci(7) + fibonacci(8) ，这两个调用之前都进行过，这就是缓存结果的原因。如果你不缓存每次调用的结果，你会浪费时间计算同样的事情两次......

顺便说一句:这段代码非常“condesed”，并且可以工作，因为规范说赋值表达式(cache[n] = ...)计算为指定的值，您将返回cache[n] ，本质上。