递归---斐波那契

从第三项起，每一项的数都是紧挨着它前面的两项的数字之和

千万记住：斐波那契的场景只是巧合。。。


有一个序列，首两项为0,1，以后各项值为前两项值之和，写一个方法来
实现这个序列的和

这就是著名的斐波那契哦。。。。

public static int getNumber(int curCount){
	  if(curCount == 1){
		  return 0;
	  }else  if(curCount == 2){
		 return 1;
	  }else{
		  int s = getNumber(curCount-1)+getNumber(curCount-2);
		  return s;
	  }
	}

/*这里只能得到当前的值。。。各项值为前两项值之和---说明要得到每一项的值需要递归
那么我要计算总数呢。。。如果用这个递归函数的话，则用最傻的方法。。循环的get每一值，显然效率不高。。。怎么办。。？？？

换思维方式：  如果我要求和：Sn = an + Sn-1 这个式子要求已知an才可以用。。。新定义一种求和：  Sn = a1 + Sn-1  其中Sn-1 = a2+a3+a4+ ...+ an 这样的话a1是已知的了
注意：只能用递归的观点来理解，sum(int n) 就是计算前n项之和，如果n=2 那么代表前两个数之和 1+0 =1 这里返回1 ，n=1 其实没有什么含义，只是为了兼容n=1的情况，完全可以不要，当n>2时，我们先计算 curC + sum(curB, curC,n-1); 也就是a3+a4+...an-3,最后计算
a1+a2,从运行的宏观顺序来看是这样的。
*/
	public static int sum(int curA, int curB,int n) { //计算前n项的和 
		if(n==2){
			return 1;  //如果前n项计算完毕则返回,注意第一项和第二项已经不用计算了
		}else if(n == 1){
			return 0;
		}else{
			int curC = curA+curB;  //这个是这一步求出来的数，作为下一步的B
			return curC + sum(curB, curC,n-1);  
		}
	}//与先前不同的是初始值应该设置进去，因为这是递推式的递归


public static int sum(int curA, int curB,int n,int startA,int startB) { //计算前n项的和 
		if(n==2){
			return startA+startB;  
		}else{
			int curC = curA+curB;  
			return curC + sum(curB, curC,n-1);//先计算a3+a4+...到了终止的时候再加a1+a2  
		}
	}





斐波那契的应用：
有一对兔子从出生后第三个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少

像这种场景----请记住---它就是斐波那契场景，因为人们通过最笨的办法数这个兔子总数的时候，发现出生的兔子数符合斐波那契规律，所以才能用斐波那契来求。。。我们把这道题作为一个模板，以后看到类似的情况，就先猜想他是不是斐波那契，如果是，那么直接用斐波那契就简单许多，注意：这里是数出来的东西符合斐波那契，而不是他很清楚的具有斐波那契语义

因为这种东西很晕，所以我把兔子分成两类，第一类是可以生的，第二类是不可以生的

                  1   2   3   4   5   6   7   8   9   10
可以生的          1   1   1   1   2   3   5   8   13  21
离可以生1个月      0   0       1   1   2   3   5   8   13
离可以生2个月              1   1   2   3   5   8   13  21

这样就不晕菜了。。。
然后汇总一下：
1   2   3   4   5   6   7   8   9    10
1   1   2   3   5   8   13  21  34   55

注意：如果把题目改成有一对兔子从出生后第四个月起。。。。那么他就不是斐波那契数列了，只是这个题目恰好他的数列是斐波那契，才可以用这个函数来求解而不用考虑他的语义，如果改掉之后就只能用面向对象来做了。。。

//用递归
private static long rabbit(int monthNum) {
   if(monthNum == 1 || monthNum == 2){
    return 1L;
   }else{
    return rabbit(monthNum-1) + rabbit(monthNum-2);
   }
}
}

树枝生长问题：

一棵树一年后长出一条新枝，新枝隔一年后成为老枝老枝便可每年长出一条新枝，如此下去，十年后树枝将有多少？

蜜蜂的路径问题：

一只蜜蜂从蜂房 A 出发，想爬到 1 ， 2 ， 3…… ， n 号蜂房，但只允许它自左向右（不许反方向倒走） . 则它爬到各号蜂房的路线数各是多少？
   1   3   5   7 。。。 n-1
bee  2   4   6。。。。n-2  n  

蜜蜂爬进n 号蜂房有下面两种途径： 一．不经过n-1 号蜂房，直接从n-2 号蜂房进入第 n号蜂房的路线有f(n-1) 条； 二．经过n-1 号蜂房进入第n 号蜂房的路线有f(n) 条 . 所以就有f(n+1)=f(n)+f(n-1) . 即 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 ……



1，有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
答：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，1，2，3，5，8，13……登上十级，有89种。
2，数列中相邻两项的前项比后项的极限是多少，就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。