Java實現(xiàn)簡單的遞歸操作方法實例
前言
在數(shù)據(jù)結(jié)構(gòu)算法設(shè)計中，或者一個方法的具體實現(xiàn)的時候，有一種方法叫做“遞歸”，這種方法在思想上并不是特別難，但是實現(xiàn)起來還是有一些需要注意的。雖然對于很多遞歸算法都可以由相應(yīng)的循環(huán)迭代來代替，但是對于一些比較抽象復(fù)雜的算法不用遞歸很難理解與實現(xiàn)。
遞歸分為直接遞歸和間接遞歸，就簡單分享一下兩個小的直接遞歸。
對于遞歸的概念，其實你可以簡單的理解為自己定義自己，記得小時候看過一部電視劇《狼毒花》，里面主角叫做“常發(fā)”，但是個文盲，老師問他叫什么，他說“常發(fā)”?！澳膫€常？”“常發(fā)的常??！”“哪個發(fā)？”“常發(fā)的發(fā)啊！”結(jié)果第二節(jié)課老師就讓一群小朋友一起喊“常發(fā)的常，常發(fā)的發(fā)，傻瓜的傻，傻瓜的瓜”。言歸正傳，顯然在多數(shù)情況下遞歸是解釋一個想法或者定義的一種合理方法。在思想上遞歸類似于數(shù)學(xué)中曾經(jīng)學(xué)過的數(shù)學(xué)歸納法。
遞歸的實現(xiàn)：
遞歸的實現(xiàn)要注意有兩點：一個遞歸的選項和一個非遞歸的選項，后者成為基礎(chǔ)情形（base case）?；A(chǔ)情形是遞歸的終結(jié)情形，沒有基礎(chǔ)情形或者處理不好都會導(dǎo)致無窮遞歸，這是我們不想要的結(jié)果。遞歸實現(xiàn)起來最關(guān)鍵的是處理好基礎(chǔ)情形。 結(jié)合具體事例在說一下遞歸回溯的過程。
下邊來寫兩個小程序：
1、爬樓梯算法：已知一個樓梯有n個臺階，每次可以選擇邁上一個或者兩個臺階，求走完一共有多少種不同的走法。
方法如下：
遞歸函數(shù)有返回值的比沒有返回值的麻煩一點，因為一個函數(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)而分析這個路徑或者說是實現(xiàn)的過程。
需要注意的是，這個算法實現(xiàn)思路上簡單，但是復(fù)雜度并沒有降低，還牽扯回溯保存堆棧問題(其實遞歸的設(shè)計盡量避免這種嵌套兩個的遞歸方式（climb（n）中包含climb（n-1）和climb（n-2）），這種操作會使得堆棧開辟空間隨著n的增大以指數(shù)型增長，最終程序很容易崩潰），而且在臺階數(shù)目多到一定數(shù)量的時候會越界（走法次數(shù)會超出int的范圍），所以遞歸程序很大程度上就是思想實現(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í)一下。
漢諾塔問題：一次只能移動一個盤子；不能把大盤子放在小盤子上；除去盤子在兩個柱子之間移動的瞬間，盤子必須都在柱子上。（在這三點要求下把盤子從起始柱子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表示不通，找到一條路徑從起始點（traverse函數(shù)的參數(shù)）到終點（右下角點）。
基礎(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)問題
總結(jié)
到此這篇關(guān)于Java實現(xiàn)簡單的遞歸操作的文章就介紹到這了,更多相關(guān)Java遞歸操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java多線程編程之從線程返回數(shù)據(jù)的兩種方法
從線程中返回數(shù)據(jù)和向線程傳遞數(shù)據(jù)類似。也可以通過類成員以及回調(diào)函數(shù)來返回數(shù)據(jù)。但類成員在返回數(shù)據(jù)和傳遞數(shù)據(jù)時有一些區(qū)別，下面讓我們來看看它們區(qū)別在哪2014-01-01
這篇文章主要介紹了使用logback配置按天和文件大小切割輸出日志方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
散列表（Hash?table，也叫哈希表)是根據(jù)關(guān)鍵碼值(Key?value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu),下面這篇文章主要給大家介紹了關(guān)于哈希表在算法題目中的實際應(yīng)用,文中介紹的方法是Java,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了18個Java8日期處理的實踐(太有用了)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01
這篇文章主要介紹了java解析.yml文件方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章主要介紹了springmvc與mybatis集成配置實例詳解的相關(guān)資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-09-09
導(dǎo)入項目出現(xiàn)Java多個工程相互引用異常A cycle was detected in the build path o
今天小編就為大家分享一篇關(guān)于導(dǎo)入項目出現(xiàn)Java多個工程相互引用異常A cycle was detected in the build path of project的解決辦法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
SpringBoot項目中處理返回json的null值(springboot項目為例)
本文以spring boot項目為例給大家介紹SpringBoot項目中處理返回json的null值問題，本文通過實例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友參考下2019-10-10
java實現(xiàn)excel導(dǎo)出合并單元格的步驟詳解
這篇文章主要介紹了java實現(xiàn)excel導(dǎo)出合并單元格,通過使用Apache POI庫，我們可以方便地創(chuàng)建Excel文件、填充數(shù)據(jù)、合并單元格和導(dǎo)出Excel文件，需要的朋友可以參考下2023-04-04
SpringBoot整合Druid數(shù)據(jù)源過程詳解
這篇文章主要介紹了SpringBoot整合Druid數(shù)據(jù)源過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-12-12