遞歸

定義：在一個方法（函數）的內部調用該方法（函數）本身的編程方式

簡而言之就是 “自己調自己”

在玩游戲之前讓我們先對遞歸有一個簡單的了解吧！

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 漢諾塔游戲鏈接：http://www.4399.com/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

對了，看到這里你就可以去把漢諾塔游戲玩通關了

總結

以上是生活随笔為你收集整理的【使用递归玩通关汉诺塔游戏】算法01-递归(斐波那契数列、汉罗塔问题)-java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。