斐波纳契（Fibonacci）数列的第一项是1，第二项是1，以后各项都是前两项的和。
例子：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..

1.求斐波那契数列第N项的值

  1. //递归
  2. function fibonacci(n) {
  3.     if (n < 1) {
  4.         return '你输入的数字不合法'
  5.     }
  6.     if (n <= 2) {
  7.         return 1;
  8.     }
  9.     return fibonacci(n - 1) + fibonacci(n - 2);
  10. }
  11. console.log(fibonacci(4));  //3
  13. //非递归
  14. function fibonacci(n) {
  15.     if (n <= 2) {
  16.         return 1;
  17.     }
  18.     let f1 = 1;
  19.     let f2 = 1;
  20.     let temp = 0;
  21.     for (let i = 3; i <= n; i++) {
  22.         temp = f1 + f2;
  23.         f1 = f2;
  24.         f2 = temp;
  25.     }
  26.     return temp;
  27. }
  28. console.log(fibonacci(4));  //3

2.自定义斐波那契数列的第一项和第二项

  1. function fibonacci(one, two, index) {
  2.     if (index === 0) {
  3.         return one;
  4.     } else if (index === 1) {
  5.         return two;
  6.     } else {
  7.         return fibonacci(one, two, index - 2) + fibonacci(one, two, index - 1);
  8.     }
  9. }
  10. // 1,3,4,7,11,18,29,47
  11. console.log(fibonacci(1, 3, 6)); // 29
  12. console.log(fibonacci(1, 3, 7)); // 47

3.缓存优化版斐波那契函数
通过自调用函数采用闭包的方式将运算的结果存放在数组里，避免重复计算

//index对应的是数组索引，如果想拿第5项的值，对应的索引是4
const fibonacci = (function () {
    let memory = [];
    return function (index) {
        if (memory[index] !== undefined) {
            return memory[index]
        }
        return memory[index] = (index === 0 || index === 1) ? 1 : fibonacci(index - 1) + fibonacci(index - 2);
    }
})()
console.log(fibonacci(4));

3.应用

爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
    var climbStairs = function (n) {
 let f1 = 1;
 let f2 = 1;
 let temp = 1;
 for (let i = 2; i <= n; i++) {
     temp = f1 + f2;
     f1 = f2;
     f2 = temp;
 }
 return temp;
};
climbStairs(3); //3