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