递归

定义：在一个方法（函数）的内部调用该方法（函数）本身的编程方式

简而言之就是 “自己调自己”

在玩游戏之前让我们先对递归有一个简单的了解吧！

5.1 递归简介

递归必须有一个出口，也就是说必须有一个限制条件，不能无限制的自己调用自己，否则会出现栈溢出的错误

我们看一个最简单的递归代码：

public class TestRecursive {public void recursive(int index){if(index>0){System.out.println("我在递归哦！"+index);recursive(--index);}}public static void main(String[] args) {new TestRecursive().recursive(3);}}

结果：

我在递归哦！3我在递归哦！2我在递归哦！1

以上递归的结束条件就是index>0

下面我们来看两个递归的应用：斐波那契数列和汉罗塔问题

5.2 斐波那契数列

斐波那契数列：1,1,2,3,5,8,13,… （每一项数大小等于其前两项之和）

要求第n项斐波那契数是多少

代码：

public class Test_Febonacci {public static void main(String[] args) {System.out.println(febonacci(5));}//斐波那契：1 1 2 3 5 8 13...public static int febonacci(int n){//第一项和第二项直接返回1if(n==1||n==2){return 1;//从第三项开始，每一项都等于前两项之和}else{return febonacci(n-1)+febonacci(n-2);}}}

结果：

5

5.3 汉诺塔问题

5.3.1 简介

我们先来玩一个汉诺塔游戏吧

(4399 汉诺塔游戏链接：/flash/109504_1.html)

感兴趣的同学可以先去玩一玩再回来接着看

汉诺塔游戏规则如下：

第一关很简单，这里就跳过了

第2关：

解法：第1个盘子->第2根柱子

第2个盘子->第3根柱子

第1个盘子->第3根柱子

第三关的步骤就较为复杂了，但是应该也能看出来，这里就不列出来了

通过上面简单的游戏，我们可以得到如下过关步骤

先把最下面的盘子以上的全部盘子移动到第二根柱子(递归)将做下面一个盘子移动到第三柱子最后将第二个柱子上面的所有盘子移动到第三柱子(递归)

这里有人就会说了：游戏规则不是一次只能移动一个盘子吗

对，每错，虽然我们一次只能移动一个盘子，但是以上的1.3步骤都是要通过递归来移动盘子的。

而我们递归结束的条件就是只有一个盘子，上代码：

5.3.2 代码

public class Hanoi {/**** @param n 盘子个数* @param from 移动的起始位置* @param mid 移动需要借助的位置* @param to 移动的终点位置*/public static void hanoi(int n,char from,char mid,char to){//如果只有一个盘子if(n==1){System.out.println("将第1个盘子从"+from+"移到"+to);//多个盘子，无论多少个盘子看成两个盘子：最下面一个盘子和上面所有盘子}else{//1.将上面所有盘子移动到中间位置midhanoi(n-1,from,to,mid);//2.将最后一个盘子移动到目标位置toSystem.out.println("将第"+n+"个盘子从"+from+"移到"+to);//3.最后将中间位置的盘子移动到tohanoi(n-1,mid,from,to);}}//测试public static void main(String[] args) {hanoi(4,'A','B','C');}}

结果：

一个盘子

将第1个盘子从A移到C

两个盘子时

将第1个盘子从A移到B将第2个盘子从A移到C将第1个盘子从B移到C

三个盘子时

将第1个盘子从A移到C将第2个盘子从A移到B将第1个盘子从C移到B将第3个盘子从A移到C将第1个盘子从B移到A将第2个盘子从B移到C将第1个盘子从A移到C

对了，看到这里你就可以去把汉诺塔游戏玩通关了