算法(1) 斐波那契数列

本文针对斐波那契数列的求值方法，分别采用递归法、尾递归法和迭代法进行分析，并提供其相关的代码实现。

今天看到公司笔试的一道算法题，题目如下：

存在如下斐波那契数列： 

0, 1, 1, 2, 3, 5, 8, 13, 21...

请编写函数，计算数列中第n项的值。

一、递归

经过简单思考后，我们可以很容易的想到，可以采用递归的方式进行代码编写，因为第n项的值等于第n-1项和第n-2项的和，实现代码如下：

function Fib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fib(n - 2) + Fib(n - 1);
}

function (n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return arguments.callee(n - 1) + arguments.callee(n - 2);
}

二、尾递归

然而，这种方式进行n值较大的计算时，非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。这时，我们可以考虑采用尾递归的模式，实现代码如下：

function Fib(n, ret1 = 0, ret2 = 1) {
    if (n == 0) return ret1;
    return Fib(n - 1, ret2, ret1 + ret2);
}

通过尾递归的方式，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。前面的代码需要保存2n个数据记录，复杂度O(n)。如果改成尾递归，只保留3个数据记录，复杂度O(1)。

尾递归实现的方式，在思路上采用了从前往后计算的方法，等效于使用了一个正向的while循环。而前面的递归采用的是从后往前倒推的方式。

三、迭代法

我们还可以采用一个迭代的方法，代码如下：

function Fib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    let [num1, num2, num3] = [1, 1, 1];

    while (n > 2) {
        [num3, num1, num2] = [num1 + num2, num2, num1 + num2];
        n--;
    }
    return num3;
}

迭代实现的方法其实与尾递归是一个道理，迭代法比较通俗易懂，而且和尾递归比较起来，因为不用开辟栈空间，所以相对而言，迭代法的效率是最高的。

四、生成器

学习了Generator生成器后，发现还可以采用生成器的方案来完成，代码如下：

function* Fib() {
    let [pre, cur] = [0, 1];
    for (;;) {
        [pre, cur] = [cur, pre + cur];
        yield cur;
    }
}

for (let n of Fib()) {
    if (n > 1000) break;
    console.log(n);
}

参考文献

1. ESMAScript 6 入门 —— 阮一峰