前端JS算法之斐波那契数列

斐波那契：由0和1开始，之后的斐波那契数列每一项都等于前两项之和。
斐波那契数列示例：1、1、2、3、5、8、13、21、34

逻辑步骤：
1、求第n项的斐波那契数，就是就n项的前两项相加，前一项是n-1,前两项就是n-2。
2、第n项斐波那契数就是(n-1) + (n-2)，这样我们就可以使用递归。
3、递归是什么？递归就是函数自己调用自己。
4、自己调用自己，那我们就可以用arguments.callee。（PS：arguments是一个类数组对象，它包含着传入函数的所有参数。arguments有一个属性callee，该属性是一个指针，指向拥有这个arguments对象的函数）

接下来看代码
第一种方法：

function fibonacci(n) {
    /*
        斐波那契数列前两项都是1，所以判断n是否等于1或者2，如果是则直接返回1
    */
    n = n && parseInt(n);
    if (n == 1 || n == 2) {
        return 1;
    };
    // 使用arguments.callee实现递归
    return arguments.callee(n - 2) + arguments.callee(n - 1);
}
let sum = fibonacci(8)
console.log(sum) // 21

我们虽然使用递归实现了输出第n项的斐波那契数，但是，递归太浪费浏览器资源了，如果第n项数字太大，运行速度将会大大加长，所以我们使用for循环优化一下。

第二种方法：

function fibonacci(nub) {
    let n = nub && parseInt(nub);
    let n1 = 1; // 初始 n = 1时候的值为1
    let n2 = 1; // 初始 n = 2时候的值为1
    let f;    // 声明变量sum 接受第 n 个的斐波那契数
    
    // n 等于 1 或 n 等于 2 的时候直接返回1
    if(n == 1 || n == 2) {
        return 1;
    }
    for(let i = 2; i < n; i++) {
        f = n1 + n2;
        n1 = n2;
        n2 = f;
    } 
    return f
}
let sum = fibonacci(8) 
console.log(8) // 21

第三种方法：

function fibonacci(n) {
    n = n && parseInt(n);
    let n1 = 1; 
    let n2 = 1;
    // n 等于 1 或 n 等于 2 的时候直接返回1
    if(n == 1 || n == 2) {
        return 1;
    }
    // 使用解构赋值，n1 等于 n2，n2 等于 n1 + n2 最后返回 n2
    for (let i = 2; i < n; i++) {
        [n1, n2] = [n2, n1 + n2]
    }
    return n2
}