一、扫盲

斐波那契数列也叫黄金分割数列，也叫兔子数列
原理：假定一对大兔子每月能生一对小兔子，且每对新生的小兔子经过一个月可以长成一对大兔子，如果不发生死亡，且每次均生下一雌一雄，问一年后共有多少对兔子？

月份 兔子情况 总数
第0个月 a（小兔子） 1
第1个月 a（具备繁殖能力） 1
第2个月 b（生啦生啦）+ a（他父母） 2
第3个月 b（2月份出生的具备繁殖能力，正跃跃欲试） + b2（他父母又生二胎了） +a（他父母） 3
第4个月 c（2月份的兔子b喜当爹）+b（二月份出生的兔子） + b2（二胎具备繁殖能力，准备生娃） +a（他父母）+d(a生三胎) 5
… … …

1、1 、2、3、5、8、13、21、34、55、89……
所以规律就是 fn(n)=fn(n-1)+fn(n-2)

二、代码实现

1.第一种

这种是最常见的实现：
迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
*i 月份
*/
function fn(i){
	var a=[];
	/*0个月什么都不存在*/
	a[0]=0;
	a[1]=1;
	for(var o=2;o<=i;o++){
		a[o]=a[o-1]+a[o-2];
	}
	return a[i]
}

2.第二种

递归

1
2
3
4
5
6
7
/*
* i 月份
*/
function fn(i){
	if(i<=1){return 1}
	return fn(i-1)+fn(i-2)
}

是不是感觉很简洁

三、缺陷

针对这个例子来说，这里的递归会进行太多次的调用（比迭代多），所以简洁的背后牺牲的是性能

四、优化

上面的递归非常消耗性能，所以要优化一下

1. 关于优化的思路

是什么导致上面的性能消耗大的？，可以看到，递归的循环次数非常多，且没有尾调用

我们知道，函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。

所以每一次的fn执行都会增加一个调用帧，导致内存消耗变大

1
2
3
4
function fn(i,prev=1,current=1){
	if(i<=1){return current}
	return fn(i-1,current,prev+current)
}