5

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

我已经做了一年多的前端开发人员了。我上学是为了学习 Web 开发，我认为自己在处理简单的 JavaScript 方面是一个有能力的程序员。但是当涉及到编写任何类型的斐波那契函数时，我无法做到。就好像我的大脑中缺少了一块可以理解如何处理这个简单数字序列的东西。这是一段工作代码，我很确定我是从 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 个斐波那契数，因为如果我能做到，那么我会觉得我至少理解了它。

因此，当前两个条件失败时，代码会创建一个新的缓存变量并将其设置为等于 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 对为什么会发生这种情况有任何帮助吗？

4

3 回答 3

3

好吧，让我们从你理解的（或说你理解的）开始：

fibonnaci 被分配了一个立即调用的函数表达式（或自执行等等等等），使用传递的任何参数启动缓存。

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

如果争论已经在缓存中，我们只需将其归还并过着永恒的和平生活。如果参数为 1 或更少，这也是函数的结束，永恒的和平再次发生。但 [...]

好吧， nowcache不会在每个函数调用上一遍又一遍地创建（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] = fibonacci(8) + fibonnaci(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]

于 2013-09-24T12:00:00.050 回答
1

好问题。用递归的方式思考是很棘手的。如果你试图掌握所有的过程，你可能会惨败。我记得因为你不理解河内塔问题的递归解决方案而感到沮丧。我试图在纸上追踪步骤的顺序，但这对理解正在发生的事情的魔力没有任何帮助。

它对我有用的是认为递归函数是一种“预言机”，它知道函数fib(i)对于任何值的返回值i < n。如果预言机知道fib(n-1)和fib(n-2)，那么它只需要给出指令来根据fib(n)这些已知值进行计算。因此，我们可以说oracle这个函数也知道 的值fib(n)。

一个警告：所有递归函数都有一个棘手的部分，我们至少需要一个在开始过程时已知的非递归值，否则我们将有一个无限递归。在斐波那契示例中，这些值为：fib(0) = 0和fib(1) = 1

您的示例比这要复杂一些，就像使用 memoization 一样，一种将 的值存储fib(n)在缓存中以避免重新计算它们的技术。在这种情况下，此缓存是一个稀疏数组（带有“孔”的数组），它在其位置 i 存储fib(i)第一次计算的值。这是一种避免在下一次fib(i)请求相同的值时重复昂贵的计算的方法。

回答您的问题：

  1. fib(n-2)不需要知道fib(n)要计算的值，它需要的是fib(n-3)和的值fib(n-4)。唯一要做的就是调用它们来询问“神谕”它们的值。
  2. 这取决于，有线性递归函数和树形递归函数，这取决于它们使用了多少其他值。在这种情况下，您有一个树形调用顺序。（实际上记忆化使它更复杂，我将其表示为有向无环图而不是树，但这与讨论无关）。
  3. 继续想一想，有一天你会有一个“啊哈”的时刻，然后递归函数对你来说会变得很明显。

如果您仍想跟踪此函数的执行，则可能有助于将您的计算重构为等效方式，因为它使执行顺序更加明显：

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

var fib2 = fibonacci(n - 2); 
var fib1 = fibonacci(n - 1);

var result = fib2 + fib1;
cache[n] = result;
于 2013-09-24T13:00:11.790 回答
0

我知道这个问题有点老了，答案很有帮助。我在 GoLang 中做这个练习，并思考如何用 Javascript 编写，并使用这个答案来刷新我的想法。我看到您的代码有一个缓存变量来存储 fib(n-2) + fib(n-1) 迭代的值。如果您正在执行递归，则不需要变量来存储结果，因为每次调用该函数时它都会返回一个数字，并且这些数字会被添加到第一个函数调用中。

function fib(n) {
    if (n<=1) return n;
    return fib(n - 1) + fib(n - 2);
}

要查看为什么不需要缓存变量，请遍历每个函数调用，并开始计算一旦n等于 1 或 0 的值。

例如：

iteration 1)

fib(3) {
   return fib(3-1) + f(3-2)   
}
---------------------------    
iteration 2)

fib(3-1) {
   return fib(2 - 1) + fib(2-2)
}

iteration 3)

fib(3-2) {
   return 1
}    
---------------------------

iteration 4)

fib(2-1) {
   return 1
}


iteration 5)
fib(2-2) {
   return 0
}
----------------------

如果你从迭代5向后计算它的返回值）

5) 0
4) 1
3) 1
2) 1 <== 4) + 5)  = 1 + 0  
1) 2  <== 2) + 3)  = 1 + 1

所以 fib(3) 是 2

于 2015-02-21T04:14:54.620 回答