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）。基礎(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)文章
spring boot 2.x html中引用css和js失效問題及解決方法
這篇文章主要介紹了spring boot 2.x html中引用css和js失效,需要的朋友可以參考下2018-11-11
在?MyBatis?中,配置文件分為?全局配置文件（核心配置文件）和映射配置文件,本文給大家介紹MyBatis中的配置文件相關(guān)知識,感興趣的朋友一起看看吧2023-10-10
Javaweb請求轉(zhuǎn)發(fā)及重定向?qū)崿F(xiàn)詳解
這篇文章主要介紹了Javaweb請求轉(zhuǎn)發(fā)及重定向?qū)崿F(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了spring boot整合kafka過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-02-02
簡單了解Java編程中線程的創(chuàng)建與守護(hù)線程
這篇文章主要介紹了Java編程中線程的創(chuàng)建與守護(hù)線程,是Java多線程并發(fā)編程的基礎(chǔ)，需要的朋友可以參考下2015-11-11
java中將一個List等分成n個list的工具方法(推薦)
下面小編就為大家?guī)硪黄猨ava中將一個List等分成n個list的工具方法(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
這篇文章主要介紹了flatten-maven-plugin使用，本文通過示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-07-07
詳解MyBatis?ResultSetHandler?結(jié)果集的解析過程
這篇文章主要為大家介紹了MyBatis?ResultSetHandler?結(jié)果集的解析過程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-02-02
Java的JDBC中Statement與CallableStatement對象實例
這篇文章主要介紹了Java的JDBC中Statement與CallableStatement對象實例,JDBC是Java編程中用于操作數(shù)據(jù)庫的API,需要的朋友可以參考下2015-12-12
java使用elasticsearch分組進(jìn)行聚合查詢過程解析
這篇文章主要介紹了java使用elasticsearch分組進(jìn)行聚合查詢過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-02-02