JavaScript Fibonacci细分

Question

我希望我在这里发布这个问题是好的,即使我也在其他网站上发布了这个问题.如果我没有遵循正确的协议,我道歉并请立即告诉我,以便我可以删除帖子并学习我的课程.

我已经成为一名前端开发人员已有一年多了.我去学校学习网络开发,在简单的JavaScript方面,我认为自己是一个有能力的编码器.但是当谈到编写任何类型的Fibonacci函数时,我无法做到.就好像我的大脑中缺少一块可以理解如何处理这个简单数字序列的东西.这是一段工作代码,我很确定我是从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被赋予一个立即调用的函数表达式(或自动执行blah blah blah),使用传递的任何参数向其启动缓存.如果争论已经存在于缓存中,我们就会将其归还,让我们的生活永远平静下来.如果论证是1或更少,那也是功能的终结,永久的和平再次发生.但如果这些条件都不存在,那么该函数会返回这个语句,让我感觉好像我只是一个穿着人类西装的猴子.

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

因此,当前两个条件失败时,代码会创建一个新的缓存变量并将其设置为等于fibonacci函数的结果,无论参数是否减去2,然后它将结果减去1 ....现在我的问题

• 问题1:如果从未计算过fibonacci(n),函数如何知道fibonacci(n-2)是什么？
• 问题2:递归函数是线性的,还是它们遵循的是什么顺序？
• 问题3:如果我无法理解这一点,我是否有希望成为一名程序员？

感谢您的时间.

经过这个块之后,我稍微改变了一下这个函数,看看我是否可以保留变量中的结果并输出它,只是为了看看会发生什么,我得到了一些非常意想不到的结果.

这是改变:

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 被分配一个立即调用的函数表达式（或自执行等等），通过传递任何参数来启动缓存。

不完全是：斐波那契被分配了IIFE 的返回值。有区别。在 IIFE 内部，我们看到了一份return function(n)声明。顾名思义，IIFE 是立即调用的。该函数被创建、执行，并且一旦返回，就不会在任何地方（显式）引用。函数返回，被赋值给变量fibonacci。
这个 IIFE确实创建了一个对象文字，称为cache. 这个对象驻留在 IIFE 的范围内，但是由于 JS 的范围扫描（这个答案链接到其他人......所有这些都一起解释了 JS 如何将名称解析为它们的值），这个对象仍然可以被返回的函数访问，现在分配给斐波那契。

如果参数已经在缓存中，我们只需将其返回并过上永久和平的生活。如果参数等于或小于 1，则函数也结束，再次实现永久和平。但 [...]

好吧，现在cache并不是在每次函数调用时一遍又一遍地创建（IIFE 仅被调用一次，这就是cache创建的地方）。如果返回的函数 (fibonnaci) 更改了它，则对对象的更改将保留在内存中。闭包变量，因为它cache可以用来在函数调用之间保存状态。您所说的所有其他内容（n <= 1）都是标准递归函数的东西......这是防止无限递归的条件。

但如果这两个条件都不存在，那么该函数就会返回这个语句，让我感觉自己就像一只穿着人类衣服的猴子。

嗯，这实际上是有趣的部分。这就是真正的魔法发生的地方。
正如我所解释的，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)，最后一个（返回）语句应解读为：

返回 (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)or fibonacci(0)，因为在这种情况下n<=1， 和 将返回，而不再进行任何递归调用。
另请注意，完整地编写时fibonnaci(9)，这实际上分解为fibonacci(7) + fibonacci(8)，这两个调用之前都已进行过，这就是结果被缓存的原因。如果您不缓存每次调用的结果，您将浪费时间计算同一件事两次......

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