遞歸（recursion）

思想：把一個復雜的問題拆分成一個簡單問題和子問題，子問題又是更小規模的復雜問題，循環往復

本質：棧的使用

遞歸的注意事項

• （1）需要有遞歸出口，否者就會無限遞歸造成棧溢出

• （2）每一次遞歸調用都會生成一個新的棧空間（即：執行一個方法時，就創建一個新的受保護的獨立空間（棧空間）），代碼繼續從上往下執行，如果符合條件就會一直遞歸，直到遞歸出口，最后一層一層返回值，完成函數的調用

• （3）方法的局部變量都是獨立的，不會相互應影響

• （4）當一個方法執行完畢，或者遇到return就會返回，遵守誰調用，就將結果返回給誰，同時當方法執行完畢或者返回時，該方法也就執行完畢

---

遞歸的內存機制分析

代碼示例

public class Recursion01 {public static void main(String[] args) {Tt1 = newT();t1.test(4);//輸出什么？ n=2 n=3 n=4}}class T {public void test(int n) {if (n > 2) {test(n- 1);}System.out.println("n=" + n);}
}

內存視圖分析

---

遞歸實例

案例一：階乘問題（factorial）

import java.util.Scanner;
public class recursion {public static void main(String[] args){Scanner input = new Scanner(System.in);object object = new object();System.out.print("input a number：");long n = input.nextLong();long result = object.factorial(n);System.out.print("factorial(" + n + ") is：" + result);}
}class object{public long factorial(long n){if(n == 1){return 1;}else{return n * factorial(n - 1);}}
}

案例二：猴子吃桃問題

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一個！以后每天猴子都吃其中的一半，然后再多吃一個。當到第 10 天時，想再吃時（即還沒吃），發現只有 1 個桃子了。問題：最初共多少個桃子？

public class recursion {public static void main(String[] args){method t = new method();int res = t.peach(1);System.out.print(res);}
}class method{public int peach(int day){if(day == 10){return 1;} else if(day >= 1 && day <= 9){return ( peach(day + 1) + 1 ) * 2;   // 枚舉每天的情況找規律得到}else{return -1;}}
}

案例三：斐波那契數列

1,1,2,3,5,8,13…給你一個整數 n，求出它的值是多少？

特點：從第三個數開始，后一個數等于前面兩個數之和

//斐波那契數列：1,1,2,3,5,8,13...public class recursion {public static void main(String[] args){method t = new method();int res = t.fibonacci(10);System.out.print(res);}
}class method{public int fibonacci(int n){if(n == 1 || n == 2){return 1;}else{return fibonacci(n - 1) + fibonacci(n - 2);}}
}//輸出：55

案例四；漢諾塔

有趣的小故事

• 漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序攥著 64 片圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

• 假如每秒鐘移動一次，共需多長時間呢？移完這些金片需要 5845.54 億年以上，太陽系的預期壽命據說也就是數百億年。真的過了 5845.54 億年，地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

思路分析：可以把這個問題拆分

• （1）把最底層移動到C塔

• （2）把上面的n-1個圓盤看作整體，移動到B塔

• （3）上面的n-1個圓盤又可以拆分成如上的問題，不斷遞歸下去

//斐波那契數列：1,1,2,3,5,8,13...public class recursion {public static void main(String[] args){tower t = new tower();t.move(3, 'a', 'b', 'c');}
}class tower{// 移動的圓盤個數， A塔 ，B塔 ， C塔public void move(int num, char a, char b, char c){if(num == 1){System.out.println(a + "->" + c);}else{// 把上面的 n-1 個圓盤從 a塔 移動到 b塔，中間借助 c 塔move(num -1, a, c, b);// 把最下面的圓盤移動到 c塔System.out.println(a + "->" + c);// 把 b塔 的所有盤移動到 c塔，中介借助 a塔move(num -1, b, a, c);}}
}//輸出
a->c
a->b
c->b
a->c
b->a
b->c
a->c

迷宮問題

思路：運用二維數組表示迷宮，初始位置為（1，1），走到出口處，標記路線

• 0表示可以走（還未被標記）

• 1表示障礙物

• 7表示可以走（被標記后）

• 3表示走過，但是走不通是死路

代碼示例

public class migong {public static void main(String[] args){int[][] map = new int[8][7];//標記墻面的部分for(int i = 0; i < 8; i++){map[i][0] = 1;map[i][6] = 1;}for(int i = 0; i < 7; i++){map[0][i] = 1;map[7][i] = 1;}map[3][1] = 1;map[3][2] = 1;// 回溯測試：輔助理解方法調用完成后棧空間釋放，是如何返回的
//        map[2][2] = 1;// 封閉路徑，測試結果
//        map[2][1] = 1;
//        map[2][2] = 1;
//        map[1][2] = 1;// 調用方法t finder = new t();finder.findway(map,1,1); // 起點是（1，1）//打印找路結果for(int i = 0; i < map.length; i++){for(int j = 0; j < map[i].length; j++){System.out.print(map[i][j] + " ");}System.out.println("");}}
}class t{public boolean findway(int[][] map, int i, int j){// 找路策略：下右上左// 如果找到了就出口返回 trueif(map[6][5] == 7){return true;}else{if(map[i][j] == 0){//假設當前點使用探路策略可以走通，就說明可以和之前的點銜接起來構成一條可以走通的路線map[i][j] = 7;// 接著使用找路策略開始探路，驗證當前點開始是否可以走通//往下走if(findway(map, i+1, j)){return true;}// 往右走else if(findway(map, i, j+1)){return true;}// 往上走else if(findway(map, i-1, j)){return true;}// 往左走else if(findway(map, i, j-1)){return true;}// 都走不通，走過了但是走不通就標記為 3else{map[i][j] = 3;return false;}}else{  // 此時 map[i][j] = 1, 7, 3 ; 7 表示測試過了就不要再重復測試return false;}}}
}

理解：沒走到一個點，就會遞歸的使用下->右->上->左的方式進行探路，如果都走不通就會返回到上一次遞歸調用，繼續探路，指導找到出口為止