前言

在數據結構算法設計中，或者一個方法的具體實現的時候，有一種方法叫做“遞歸”，這種方法在思想上并不是特別難，但是實現起來還是有一些需要注意的。雖然對于很多遞歸算法都可以由相應的循環迭代來代替，但是對于一些比較抽象復雜的算法不用遞歸很難理解與實現。

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

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

遞歸的實現：

遞歸的實現要注意有兩點：一個遞歸的選項和一個非遞歸的選項，后者成為基礎情形（base case）。基礎情形是遞歸的終結情形，沒有基礎情形或者處理不好都會導致無窮遞歸，這是我們不想要的結果。遞歸實現起來最關鍵的是處理好基礎情形。 結合具體事例在說一下遞歸回溯的過程。

下邊來寫兩個小程序：

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的范圍），所以遞歸程序很大程度上就是思想實現設計上簡單理解一些。

下邊是源代碼：

1. package leetcode;
2.  
3. public class ClimbStairs {
4. // **************************************************************
5. public int climbStairs(int n) {
6. int i=1;
7. if(n<=0)
8. return 0;
9. if(n==1){
10. return i;
11. }
12. if(n==2){
13. i++;
14. return i;
15. }
16. else
17. return climbStairs(n-1)+climbStairs(n-2);
18. }
19. //**************************************************************
20. public static void main(String []args){
21. ClimbStairs cs=new ClimbStairs();
22. int a =cs.climbStairs(4);
23. System.out.println(a);
24. }
25.  
26. }

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

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

代碼如下：

基礎情形：n==1的時候終止遞歸，進行回溯。

1. public class HanNuoTower {
2. public void tower(int n,char s,char m,char e)//n個塔從s經過m最終全部移動到e
3. {
4. if(n==1)
5. move(s,e);
6. else
7. {
8. tower(n-1,s,e,m);
9. move(s,e);
10. tower(n-1,m,s,e);
11. }
12. }
13. public void move(char s,char e){
14. System.out.println("move "+s+" to "+e);
15. }
16. public static void main(String []args){
17. HanNuoTower hnt =new HanNuoTower();
18. hnt.tower(4,'A','B','C');
19. }
20.  
21. }

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

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

1. public class Maze {
2. private final int TRIED=3;
3. private final int PATH=7;
4.  
5. private int [][] grid={ {1,1,1,0,0,1,0,1,0,0},
6. {0,0,1,1,1,0,0,0,0,0},
7. {1,0,1,0,0,0,1,1,1,1},
8. {1,1,1,1,1,0,0,0,1,1},
9. {0,0,0,0,1,1,1,0,0,0},
10. {1,0,1,0,1,0,0,1,0,0},
11. {1,0,0,1,1,1,1,1,1,1} };
12. public boolean traverse(int row,int column){
13. boolean done =false;
14. if(valid(row,column))
15. {
16. grid[row][column]=TRIED;
17. if(row==grid.length-1&&column==grid[0].length-1)
18. done=true;
19. else
20. {
21. done=traverse(row+1,column);//down
22. if(!done)
23. done=traverse(row,column+1);//right
24. if(!done)
25. done=traverse(row-1,column);//up
26. if(!done)
27. done=traverse(row,column-1);//left
28. }
29. if(done)
30. grid[row][column]=PATH;
31. }
32. return done;
33. }
34. private boolean valid(int row,int column){
35. boolean result=false;
36. if(row>=0&&row<grid.length&&column>=0&&column<grid[row].length)
37. if(grid[row][column]==1)
38. result=true;
39. return result;
40. }
41. public String toString(){
42. String result="\n";
43. for (int row=0;row<grid.length;row++){
44. for(int column=0;column<grid[row].length;column++){
45. result +=grid[row][column]+" ";
46. }
47. result+="\n";
48. }
49. return result;
50. }
51. public static void main (String []args){
52. Maze maze=new Maze();
53. System.out.println(maze);
54. if(maze.traverse(0, 0))
55. System.out.println("The maze was successfully travelled!");
56. else
57. System.out.println("There is no possible path.");
58. System.out.println(maze);
59. }
60.  
61. }

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

總結

到此這篇關于Java實現簡單的遞歸操作的文章就介紹到這了,更多相關Java遞歸操作內容請搜索我們以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持我們！

原文鏈接：https://blog.csdn.net/ares_xxm/article/details/68957829