斐波拉契数列

这个数列生成规则很简单，每一项都是前两项的和，举例

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……用数学符号来描述更好

$$ F_{n}=F_{

{n-1}}+F_{ {n-2}}（n≧2） $$

递归方法求解

这个几行代码就可以解决

// n从1开始function fib(n) {    if (n <= 2)        return 1;    return fib(n - 1) + fib(n - 2);}

但是分析一下这个算法的执行过程，以f（6）为例

以上的递归树中，很多节点被重复计算，譬如f(2)就被重复执行了5次，另外，递归调用中每一个函数都要保留上下文，所以空间上开销也不小。所以这个方法并不是很理想。

循环方法求解

其实还是利用斐波拉契数列的特性

// n从1开始function fibFor(n) {    if (n <= 2)        return 1;    let arr = [];    //arr[0] = 0;    arr[2] = arr[1] = 1;    for (let i = 3; i <= n; i++) {        arr[i] = arr[i - 1] + arr[i - 2];    }    return arr[n];}

当然这个方法还可以压缩一下，因为我们没必要存储一个数组，只用三个变量就行了。

// n从1开始function fibFor2(n) {    if (n <= 2)        return 1;    let before2 = 1;    let before1 = 1;    let now = null;    for (let i = 3; i <= n; i++) {        now = before1 + before2;        before2 = before1;        before1 = now;    }    return now;}

这其实就是动态规划的思想了，自底向上，用子问题解决父问题。