算法-斐波那契数列(斐波那契数列算法框图)
一、定义
斐波那契数列fib(n)又被称为黄金分割数列，该数列由0和1开始，通俗的说话就是后面的每个数字都是前两个数字相加之和。
例如：0，1，1，2，3，5，8，13，21，34，55，89……
一般可以使用递归、缓存、递推方式解算出来。同时斐波那契是有数学公式的，矩阵，位运算等这些方面的概念。
二、递归
var fib = function(N) {
if(N == 1 || N == 0) {
return N;
}
return fib(N-1) + fib(N-2);//递推公式
}复制代码思路：
当给你的N等于1或者等于0的时候直接输出
否则就用递归的方式拿到N前一个数字和N前两个数字，然后计算出这两个数字相加之和就是当前的N。
使用递归的方法，输出数列的第N个数字，但是因为使用递归进行计算斐波那契会有大量重复的计算，这时可以使用数学公式加速。因为N是越来越大的，N的值越大，就更加可能造成内存溢出，或者计算时间长，和上图一样计算的速度很慢，虽然可以实现，但是只能适合0-30以内的数字。
三、递推
定义：递推算法是一种理想型思维模式的代表，根据已知的条件得出中间的结论，直到推出结果为止，递推算法还分为顺推和逆推两种。
顺推：根据已知的条件，求出需要解决的结果。
逆推：根据目前的问题，逐步求出条件。
递归和递推的区别：递推去掉了数据进出栈的过程，也就是不需要通过函数向边界值靠拢，而是反向来从边界值出，直到出函数值。所以递推的效率更高，但是递归也有一定的优势根据需求使用。
var fib = function(N) {
let cache = [];
for(let i = 0;i <= N;i++) {
if(i == 1 || i == 0) {
cache[i] = i;
}else {
cache[i] = cache[i-1]+cache[i-2]
}
}
return cache[N]
}复制代码这个的复杂度是O(n)，其实还可以通过数学公式优化的更好。
第一次写算法，如果有写的不好的地方不要说我啊，社恐……
作者：小鲸鱼mm
链接：https://juejin.cn/post/7033705205430665247