尾递归和斐波那契数列

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)有什么用？我已经追踪过了，但还是无法理解这是如何工作的。

- qwertymk

Answer 1

在function(n,a,b)中，n作为倒计时计数器，a和b存储两个连续的斐波那契数以计算下一个斐波那契数。因此，当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程序员所说）。

- zw324

Answer 2

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

我建议您查看这个页面，它是关于arguments对象的文档。从文档中可以得知，arguments.callee是对当前函数的引用。这必须这样做，因为他们正在使用匿名函数，所以它没有名称（至少他们不知道）。

似乎他们正在递归调用匿名定义的函数，深度为n。在此过程中，他们计算斐波那契数列，并在达到n的深度时返回值a。传递给函数的初始值为(n,0,1)

- nicholas.hauschild

Answer 3

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

具体的函数通过在内部函数中进行递归调用来计算Fibonacci数列。

- hayesgm

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 减一，同时将 a 和 b 移动到序列中的下一个数字。如果 n 等于 0，则序列完成，并返回当前数字 a。

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

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

---

话虽如此，在像 JavaScript 这样没有尾调用优化的语言中使用递归是低效的。对于大的 n，你最好使用标准的循环语句而不是递归来编写。

- Justin Ethier

---

JavaScript自ES6版本开始已经拥有了尾调用优化：http://benignbemine.github.io/2015/07/19/es6-tail-calls/ - Benny Code

语言可能支持它们，但很多实现还没有：https://kangax.github.io/compat-table/es6/ - Justin Ethier

Answer 5

我看到了一些可能会导致混淆的问题。递归函数模式的简写和尾部优化。

问题可能出在代码的简写版本上。下面是为了清晰而重新编写的代码。

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

尾部优化用于通过添加累加器部分来控制递归函数的堆栈使用。这是一种常见的模式，但会降低可读性。那就是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 是斐波那契数列的序列部分。

- Νικόλαος Μανωλακος

---

这并没有真正回答原始问题，虽然它确实让函数更加清晰明了。请添加一些关于该函数的评论，以使您的答案完整。 - Brody