尾递归和斐波那契

Question

我正在查看这个网站： http://rosettacode.org/wiki/Fibonacci_sequence#JavaScript 和看到这个程序：

function fib(n) {
  return function(n,a,b) {
    return n>0 ? arguments.callee(n-1,b,a+b) : a;
  }(n,0,1);
}

它是如何工作的，这两个参数（a和b）有什么帮助。我追踪了它，但仍然不明白这是如何工作的

Answer 1

在function(n,a,b)中，n用作倒数计数器，ab存储两个连续的斐波那契数用于计算下一个斐波那契数，因此当 n 达到 0 时，您将得到 a 作为第 n+1 个斐波那契数（因为真正的斐波那契数有两个 1 作为开头）。

例如，n=4：

n  a  b
4  0  1
3  1  2
2  2  3
1  3  5
0  5  8

如您所见，a 和 b 的值始终等于斐波那契数。此外，这与函数式编程非常相似（正如网站上所说的Scheme程序员）。

Answer 2

a 和 b 是新定义的匿名函数的参数。

我会看一下这个页面，它是有关参数 对象。从文档中，arguments.callee 是对您当前所在函数的引用。必须这样做，因为他们正在匿名函数中工作，因此它实际上没有名称（他们知道）。

看起来好像他们正在递归调用他们（匿名）定义的函数，深度为 n。在此过程中，他们会计算 fib 数，一旦满足 n 深度，就会返回值 a。传递给函数的初始值为(n,0,1)

Answer 3

正如此处所解释的，arguments.callee指的是你所在的当前函数。由于你所在的函数是匿名，所以这是调用该函数并实现的唯一方法 递归。

具体函数通过递归调用内部函数来计算斐波那契数列。

Answer 4

a和b分别表示序列的当前编号和序列的下一个编号，从0和1开始>。 n 是一个倒计时器，指定将返回斐波那契序列的哪个元素（例如：n = 10 将返回 55）。

该函数的工作原理是接受一个参数n，这意味着它将计算序列中的第n个数字：

function fib(n) {

然后该代码定义一个函数来计算序列中的下一个数字：

function(n,a,b) {
  return n>0 ? arguments.callee(n-1,b,a+b) : a;
}

基本上这个匿名函数会倒数n 每次执行时加 1，同时将 a 和 b 移动到序列中的下一个数字。如果n等于0，则序列完成并返回当前数字a。

arguments.callee 指的是当前正在执行的函数，因此代码只是意味着用新的参数回调自身。换句话说，开始“循环”的下一次迭代。

最后，通过说 (n,0,1);，代码实际上是使用参数 n,0,1 调用 fib。 return 语句（我在上面的代码片段中省略了）获取匿名函数的返回值并将其返回给 fib 的调用者。

---

也就是说，以这种方式使用递归对于 JavaScript 等没有尾调用优化的语言来说效率很低。对于较大的n，您最好使用标准循环结构而不是递归来编写它。

Answer 5

我发现一些可能导致混乱的问题。递归函数模式的短手和尾部优化。

问题可能出在代码的速记版本中。为了清楚起见，下面重写了。

1. 来确认匿名函数
2. 通过给它命名“recur”条件（三元）运算符扩展

。尾部优化用于通过添加累加器部分来控制递归函数的堆栈使用。这是一种常见的模式，但会降低可读性。这就是recur 函数。

特别注意的是，与循环迭代相比，性能非常好。

function fib(n) {
    function recur(n, a, b) {
        if (n > 0) {
            return recur(n - 1, b, a + b);
        } else {
            return a;
        }
    }
    return recur(n, 0, 1);
}

对于参数来说，n是迭代计数器，a和b是斐波那契数列部分。