快捷導(dǎo)航

Java實(shí)現(xiàn)簡單的遞歸操作方法實(shí)例

更新時間：2021年02月21日 08:51:28 作者：Alex_the_Dawn

這篇文章主要給大家介紹了關(guān)于Java實(shí)現(xiàn)簡單的遞歸操作的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

在數(shù)據(jù)結(jié)構(gòu)算法設(shè)計中，或者一個方法的具體實(shí)現(xiàn)的時候，有一種方法叫做“遞歸”，這種方法在思想上并不是特別難，但是實(shí)現(xiàn)起來還是有一些需要注意的。雖然對于很多遞歸算法都可以由相應(yīng)的循環(huán)迭代來代替，但是對于一些比較抽象復(fù)雜的算法不用遞歸很難理解與實(shí)現(xiàn)。

遞歸分為直接遞歸和間接遞歸，就簡單分享一下兩個小的直接遞歸。

對于遞歸的概念，其實(shí)你可以簡單的理解為自己定義自己，記得小時候看過一部電視劇《狼毒花》，里面主角叫做“常發(fā)”，但是個文盲，老師問他叫什么，他說“常發(fā)”?！澳膫€常？”“常發(fā)的常??！”“哪個發(fā)？”“常發(fā)的發(fā)??！”結(jié)果第二節(jié)課老師就讓一群小朋友一起喊“常發(fā)的常，常發(fā)的發(fā)，傻瓜的傻，傻瓜的瓜”。言歸正傳，顯然在多數(shù)情況下遞歸是解釋一個想法或者定義的一種合理方法。在思想上遞歸類似于數(shù)學(xué)中曾經(jīng)學(xué)過的數(shù)學(xué)歸納法。

遞歸的實(shí)現(xiàn)：

遞歸的實(shí)現(xiàn)要注意有兩點(diǎn)：一個遞歸的選項和一個非遞歸的選項，后者成為基礎(chǔ)情形（base case）?；A(chǔ)情形是遞歸的終結(jié)情形，沒有基礎(chǔ)情形或者處理不好都會導(dǎo)致無窮遞歸，這是我們不想要的結(jié)果。遞歸實(shí)現(xiàn)起來最關(guān)鍵的是處理好基礎(chǔ)情形。結(jié)合具體事例在說一下遞歸回溯的過程。

下邊來寫兩個小程序：

1、爬樓梯算法：已知一個樓梯有n個臺階，每次可以選擇邁上一個或者兩個臺階，求走完一共有多少種不同的走法。

方法如下：

遞歸函數(shù)有返回值的比沒有返回值的麻煩一點(diǎn)，因?yàn)橐粋€函數(shù)只有一個返回值，但是遞歸還要求有基礎(chǔ)情形的存在，所以還必須有if判斷來終止遞歸。所以在每一個if或者else后邊都有一個return，這樣保證函數(shù)在任何一種情況下都有且僅有一個返回值。

分析一下這個算法：

A：如果有0個臺階，那么有0種走法，這個不用多說；

B：如果有1個臺階，那么有1種走法；

C：如果有2個臺階，那么有2種走法（一次走1個，走兩次；一次走兩個）；

以上的B和C就是基礎(chǔ)情形。

D：接下來就是遞歸了，如果臺階數(shù)目多于2個，那么首先第一步就有兩種選擇：第一次走1個，或者第一次走兩個。這樣除了第一次后邊的走法就有了兩種情形：climbStairs(n-1)和climbStairs(n-2)。這樣一直遞歸下去，直到出現(xiàn)到了基礎(chǔ)情形（即n=1或n=2的情形），遞歸到這個地方（基礎(chǔ)情形），然后開始回溯，這就是所說的和遞歸密切相關(guān)的“回溯”了?；厮?，顧名思義就是從結(jié)果倒著回去，找到整個過程，進(jìn)而分析這個路徑或者說是實(shí)現(xiàn)的過程。

需要注意的是，這個算法實(shí)現(xiàn)思路上簡單，但是復(fù)雜度并沒有降低，還牽扯回溯保存堆棧問題(其實(shí)遞歸的設(shè)計盡量避免這種嵌套兩個的遞歸方式（climb（n）中包含climb（n-1）和climb（n-2）），這種操作會使得堆棧開辟空間隨著n的增大以指數(shù)型增長，最終程序很容易崩潰），而且在臺階數(shù)目多到一定數(shù)量的時候會越界（走法次數(shù)會超出int的范圍），所以遞歸程序很大程度上就是思想實(shí)現(xiàn)設(shè)計上簡單理解一些。

下邊是源代碼：

package leetcode;

public class ClimbStairs {
//	**************************************************************
	public int climbStairs(int n) {
 int i=1;
		 if(n<=0)
			return 0;
		 if(n==1){
			 return i;
		 }
		 if(n==2){
			 i++;
			 return i;
		 }
		 else
			 return climbStairs(n-1)+climbStairs(n-2);
 }
//**************************************************************
 	 public static void main(String []args){
		 ClimbStairs cs=new ClimbStairs();
		 int a =cs.climbStairs(4);
	 	 System.out.println(a);
	 }

}

然后還有幾個比較典型的遞歸問題：比如說迷宮問題，或者最經(jīng)典的漢諾塔問題，下邊都給出源碼，大家一塊兒學(xué)習(xí)一下。

漢諾塔問題：一次只能移動一個盤子；不能把大盤子放在小盤子上；除去盤子在兩個柱子之間移動的瞬間，盤子必須都在柱子上。（在這三點(diǎn)要求下把盤子從起始柱子A全部移動到目標(biāo)柱子C上）

代碼如下：

基礎(chǔ)情形：n==1的時候終止遞歸，進(jìn)行回溯。

public class HanNuoTower {
	public void tower(int n,char s,char m,char e)//n個塔從s經(jīng)過m最終全部移動到e
	{
		if(n==1)
			move(s,e);
		else
		{
			tower(n-1,s,e,m);
			move(s,e);
			tower(n-1,m,s,e);
		}
	}
	public void move(char s,char e){
		System.out.println("move "+s+" to "+e);
	}
	public static void main(String []args){
		HanNuoTower hnt =new HanNuoTower();
		hnt.tower(4,'A','B','C');
	}

}

迷宮走法：二維數(shù)組構(gòu)成一個迷宮，1表示通路，0表示不通，找到一條路徑從起始點(diǎn)（traverse函數(shù)的參數(shù)）到終點(diǎn)（右下角點(diǎn)）。

基礎(chǔ)情形：row=grid.length-1&&column=grid[0].length-1時done=true；

public class Maze {
	private final int TRIED=3;
	private final int PATH=7;
	
	private int [][] grid={	{1,1,1,0,0,1,0,1,0,0},
										{0,0,1,1,1,0,0,0,0,0},
										{1,0,1,0,0,0,1,1,1,1},
										{1,1,1,1,1,0,0,0,1,1},
										{0,0,0,0,1,1,1,0,0,0},
										{1,0,1,0,1,0,0,1,0,0},
										{1,0,0,1,1,1,1,1,1,1}		};
	public boolean traverse(int row,int column){
		boolean done =false;
		if(valid(row,column))
		{
			grid[row][column]=TRIED;
			if(row==grid.length-1&&column==grid[0].length-1)
				done=true;
			else
			{
				done=traverse(row+1,column);//down
				if(!done)
					done=traverse(row,column+1);//right
				if(!done)
					done=traverse(row-1,column);//up
				if(!done)
					done=traverse(row,column-1);//left
			}
			if(done)
				grid[row][column]=PATH;
		}
		return done;
	}
	private boolean valid(int row,int column){
		boolean result=false;
		if(row>=0&&row<grid.length&&column>=0&&column<grid[row].length)
			if(grid[row][column]==1)
				result=true;
		return result;
	}
	public String toString(){
		String result="\n";
		for (int row=0;row<grid.length;row++){
			for(int column=0;column<grid[row].length;column++){
				result +=grid[row][column]+" ";
			}
			result+="\n";
		}
		return result;
	}
	public static void main (String []args){
		Maze maze=new Maze();
		System.out.println(maze);
		if(maze.traverse(0, 0))
			System.out.println("The maze was successfully travelled!");
		else
			System.out.println("There is no possible path.");
		System.out.println(maze);
	}

}

還有一個九連環(huán)的操作，有興趣的話可以一起看看。Java遞歸解決九連環(huán)問題