递归解决斐波那契数列

1、什么是递归？

　　递归：递归是方法定义调用方法本身的现象。递归举例如下：

<span style="font-size:14px;">public class DiGuiDemo {

	//递归方法举例
	 public void show()
	 {
	     show();
	 }
}
</span>

（1）递归一定要有出口。否则就会死递归。

　　上面举例用的递归就是一个死递归，方法永远都在进行自身调用，最终一定会陷入内存崩溃。所以递归要定义出口，就是结束递归的条件。举例如下：

<span style="font-size:14px;">　　　　　　　　　　　　public void show(int n)
 			{
 				if(n==0)
 				{
 					System.exit(0);          
 				}
 				else{
 					System.out.println("hell");
 					show(n-1);
 				}
 			}</span>

（2）递归的次数不要过多，否则调用方法太多会导致内存空间溢出。

（3）构造方法不能使用递归的方式调用。

3、生活中存在的递归与递归思想？

　　编程思想来源于生活，生活中有很多的递归小例子，例如小时候经常听的故事：

　　从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事。。。。。

　　这就是递归了，可惜这个故事没有递归出口。。。

　　递归的思想：编程取材于生活然后解决特定问题，在编程中递归是将大问题分解成若干的小问题，然后再将小问题分解成更小的问题，直到分解的问题是已知的结论。

4、练手：用递归求5！

　　分析：（1）规律 ：n!=n(n-1)！   （2）出口：当递归到1！时是已知的，1！=1。

　　思路：将5！分解为5*4！；再将5*4!分解为5*4*3！。。。如图：

　　代码体现：

<span style="font-size:14px;">　public class DiGuiDemo {
	public static void main(String[] args) {
		int num = 5;
		System.out.println(jc(num));
	}

        //定义求阶乘方法
	public static int jc(int n) {
		if (n == 1) {

			return 1; <span style="font-family: Arial, Helvetica, sans-serif;">// 出口 ，如果是1，就返回1</span>

		} else {
			
			return n * jc(n - 1);  <span style="font-family: Arial, Helvetica, sans-serif;">// 规律，如果不等于1，就递归</span>

		}
	}
}</span>

　　DiGuiDemo类被加载到方法区中，当执行此类时，首先将main方法调用到栈中执行，main方法中还有jc（num）方法，于是接下来调用jc（num）方法，因为jc方法递归直到1，所以调用顺序为：main--jc(5)--jc(4)--jc(3)--jc(2)--jc(1)。因为栈这种数据结构的特点是先进后出，所以方法的执行顺序是jc(1)--jc(2)--jc(3)--jc(4)--jc(5)然后返回给main方法。内存图如下：

　　jc（1）是已知的值为1，所以将1 return 给jc（2），因为栈中调用特点为调用结束后被调用者就在栈中消失，所以这些方法会按jc(1)--jc(2)--jc(3)--jc(4)--jc(5)--main顺序依次return 回值并在栈中依次消失。

5、递归解决斐波那契数列。

　　需求：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死， 问第二十个月的兔子对数为多少？ 

　　分析：因为每对兔子从第三个月开始每个月生一对小兔子，那么第一个月有1对；第二个月1对；第三个月2对；第四个月3对；第五个月5对。。。

　　得到这样的一个数列：1，1，2，3，5，8，13，21。。。

　　规律：从第三项开始，每一项是前两项之和。

　　代码实现：

<span style="font-size:14px;">public class DiGuiDemo {
	public static void main(String[] args) {
		System.out.println(fun(20));
	}

        //定义递归方法
	public static int fun(int n) {
		 if (n == 1) {
		 return 1; //第一个月1对，返回1
		 } else if (n == 2) {
		 return 1; //第二个月1对，返回1
		 } else {
		 return fun(n - 1) + fun(n - 2); //从第三个月开始是前两个月对数之和
		 }
	}
}</span>

　　小结：递归是方法调用方法本身的情况，利用递归可以解决一些能够将问题分解成小问题的情况。但是注意递归一定要有出口，并且递归次数不宜过多。