JavaScript 斐波那契细分 [英] JavaScript Fibonacci breakdown
问题描述
我希望我在这里发布这个问题没有问题，即使我也在其他网站上发布了它.如果我没有遵守适当的协议，我深表歉意，并请立即通知我，以便我可以删除帖子并吸取教训.
I hope it is ok that I am posting this question here even though I have also posted it on other sites. If I have failed to follow proper protocols, I apologize and please let me know right away so I may remove the post and learn my lessons.
我做前端开发人员已经一年多了.我去学校学习 Web 开发，当涉及到简单的 JavaScript 东西时，我认为自己是一个有点能干的编码员.但是在编写任何类型的斐波那契函数时，我都做不到.就好像我的大脑中缺少一块可以理解如何处理这个简单的数字序列.这是一段工作代码，我很确定我是从 John Resig 的书或网上某处获得的:
I've been a front end developer for over a year now. I went to school to learn web development, and I consider myself a somewhat capable coder when it comes to simple JavaScript stuff. But when it comes to writing any type of Fibonacci function I cannot do it. It is as if I have a piece missing from my brain that would understand how to deal with this simple sequence of numbers. Here is a piece of a working code that I'm pretty sure I got from a John Resig book or somewhere online:
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
When I call this function with 10 as the argument, I get this sequence: 10,8,6,4,2,3,5,7,9
以下是我的理解:
fibonnaci 被分配了一个立即调用的函数表达式(或自执行等等)，无论传递什么参数都会启动缓存.如果争论已经在缓存中，我们只需返回它并在永恒的和平中过上我们的生活.如果参数为 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. 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 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.
我想做的是以正确的顺序生成前 10 个斐波那契数，因为如果我能做到，那么我会觉得我至少理解了它.
What I'd like to do is generate the first 10 fibonnaci numbers in the correct sequence, because if I can do that, then I'll feel like I at least understand it.
因此，当前两个条件失败时，代码会创建一个新的缓存变量并将其设置为斐波那契函数的结果，无论传入的任何参数都为负 2，然后将结果加上负 1.... 现在对于我的问题
So when the first two conditions fail, the code creates a new cache variable and sets it equal to the result of the fibonacci function with whatever argument was passed minus 2, and then it adds the result minus 1.... now for my questions
- 问题 1:如果从未计算过 fibonacci(n)，函数如何知道 fibonacci(n-2) 是什么?
- 问题 2:递归函数是线性的，或者它们遵循什么顺序?
- 问题 3:如果我不能理解这一点，我还有希望成为一名程序员吗?
感谢您的宝贵时间.
在通过这个块之后，我稍微改变了函数，看看我是否可以将结果保存在一个变量中并输出它，只是为了看看会发生什么，我得到了一些非常出乎意料的结果.
After getting past this block, I changed the function a bit to see if I could hold on to the result in a variable and output it, just to see what happens, and I got some really unexpected results.
变化如下:
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对为什么会发生这种情况有帮助吗?
Here's the resulting pattern: 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 Any help with why this happens?
推荐答案
好吧，让我们从你理解的(或者说你理解的)开始:
Well, let's start with what you understand (or say you understand):
fibonnaci 被分配了一个立即调用的函数表达式(或自执行等等)，无论传递什么参数都会启动缓存.
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的范围内，但是因为JS的范围扫描(这个答案链接到其他...所有他们一起解释了 JS 如何将名称解析为它们的值)，这个对象仍然可以被返回的函数访问，现在分配给 fibonaci.
Not quite: fibonnaci is assigned the return value of an IIFE. There's a difference. Inside the IIFE, we se a return function(n) statement. The IIFE is, as it's name suggests, invoked immediatly. the function is created, executed and, once returned, is not being referenced (explicitly) anywhere. The function is returned, is assigned to the variable fibonacci.
This IIFE does create an object literal, called cache. This object resides in the scope of the IIFE, but because of JS's scope scanning(this answer links to others... all of them together explain how JS resolves names to their values), this object is still accessible to the returned function, now assigned to fibonaci.
如果参数已经在缓存中，我们只需返回它并在永恒的和平中过上我们的生活.如果参数为 1 或更少，那也是函数的结束，永恒的和平再次发生.但是 [...]
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 可以用来保存函数调用之间的状态.您所说的所有其他内容 (n <= 1) 都是标准的递归函数……这是防止无限递归的条件.
Well, now cache is not created over and over again on each function call (the IIFE is only called once, and that's where cache is created). If the returned function (fibonnaci) changes it, that change to the object will persist in memory. Closure vars, for that is what cache is can be used to hold state between function calls. All the other things you say (n <= 1) is standard recursive function stuff... it's the condition that prevents infinite recursion.
但是如果这两个条件都不存在，那么该函数会返回这个语句，让我觉得自己就像是一只穿着人类西装的猴子.
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，而是引用返回的函数:
Well, this is actually the fun part. This is where the actual magic happens.
As I've explained, fibonnaci does not reference the IIFE, but rather, it references teh returned function:
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)语句应该读作:
This means, that every occurance of fibonacci can be replaced with the function body. When calling fibonnaci(10), the last (return) statement should be read as:
return (cahce[n] = fibonacci(8) + fibonnaci(9));
return (cahce[n] = fibonacci(8) + fibonnaci(9));
现在，如您所见，在返回值中调用了 fibonacci(8) 和 fibonnaci(9).这些表达式也可以完整地写出来:
Now, as yousee, fibonacci(8) and fibonnaci(9) are called, in the return value. These expression can be written in full, too:
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]
这就是这个缓存函数的实际关系......
That's how this cache function actually ties in...
我们可以重复这个直到我们调用 fibonnacci(1) 或 fibonacci(0)，因为在这种情况下 n<=1，并且将在没有更多递归调用的情况下返回.
还要注意，在完整地编写 fibonacci(9) 时，这实际上分解为 fibonacci(7) + fibonacci(8)，这两个调用之前都已进行过，这就是结果被缓存的原因.如果你不缓存每次调用的结果，你会浪费时间计算同样的东西两次......
We can repeat this until we call fibonnacci(1) or fibonacci(0), because in that case n<=1, and will be returned without any more recursive calls.
Also note that, in writing fibonnaci(9) in full, this actually breaks down into fibonacci(7) + fibonacci(8), both these calls have been made before, and that's why there results were cached. If you don't cache the results of each call, you'll waste time calculating the same thing twice...
顺便说一句:这段代码非常接受"，并且之所以有效，是因为规范说赋值表达式 (cache[n] = ...) 的计算结果为分配的值，本质上是返回 cache[n].
BTW: this code is very much "condesed", and works because the specs say that an assignment expression (cache[n] = ...) evaluates to the assigned value, you're returning cache[n], essentially.
这篇关于JavaScript 斐波那契细分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
