1、概念 遞歸就是方法自己調用自己,每次調用時傳入不同的變數.遞歸有助於編程者解決複雜的問題,同時可以讓代碼變得簡潔。並且遞歸用到了虛擬機棧 2、能解決的問題 數學問題 八皇後問題 漢諾塔 求階乘 迷宮問題 球和籃子 各種排序演算法 3、規則 方法的變數是獨立的,不會相互影響的 如果方法中使用的是引用 ...
1、概念
遞歸就是方法自己調用自己,每次調用時傳入不同的變數.遞歸有助於編程者解決複雜的問題,同時可以讓代碼變得簡潔。並且遞歸用到了虛擬機棧
2、能解決的問題
數學問題
- 八皇後問題
- 漢諾塔
- 求階乘
- 迷宮問題
- 球和籃子
各種排序演算法
3、規則
-
方法的變數是獨立的,不會相互影響的
-
如果方法中使用的是引用類型變數(比如數組),就會共用該引用類型的數據
-
遞歸必須向退出遞歸的條件逼近,否則就是無限遞歸,出現 StackOverflowError
-
當一個方法執行完畢,或者遇到 return,就會返回,遵守誰調用,就將結果返回給誰,同時當方法執行完畢或
者返回時,該方法也就執行完畢
4、迷宮問題
思路
- 用一個二維矩陣代表地圖
- 1代表邊界
- 0代表未做過該地點
- 2代表走過且能走得通
- 3代表走過但走不通
- 設置起點和終點以及每個地點的行走策略
- 行走策略指在該點所走的方向的順序,如 下->右->上->左(調用尋找路徑的方法,使用遞歸)
- 每次行走時假設該點能夠走通,然後按照策略去判斷,如果所有策略判斷後都走不通,則該點走不通
圖解
初始地圖,假設圓點為終點
如以下->右->上->左的策略,路線如下
代碼
public class MiGong { //用0表示沒有走過的路,用1表示牆 public static void main(String[] args) { int[][] map = new int[8][7];//創建地圖 //設置地圖的牆體,用1來表示 for (int i = 0; i < 7; i++){ map[0][i] = 1; map[7][i] = 1; } for (int i = 0; i < 8; i++){ map[i][0] = 1; map[i][6] = 1; } map[3][1] = 1; map[3][2] = 1; System.out.println("迷宮地圖:"); for (int i = 0; i < map.length; i++){ for (int j = 0; j < map[0].length; j++){ System.out.print(map[i][j]+" "); } System.out.println(); } setWay(map,1,1); System.out.println("啟動走迷宮後:"); for (int i = 0; i < map.length; i++){ for (int j = 0; j < map[0].length; j++){ System.out.print(map[i][j]+" "); } System.out.println(); } } /** * 用2表示走過的路,用3表示走過且不能繼續走下去的路 * @param map 表示地圖 * @param i 表示第i行開始找 * @param j 表示第j列開始找 * @return 返回true的時候表示可以走,返回false的時候表示不能走 */ public static boolean setWay(int[][] map, int i, int j){ if (map[6][5] == 2){//設map[6][5]這個位置是迷宮終點,當終點為2的時候表示迷宮走通了 return true; }else { if (map[i][j] == 0){ map[i][j] = 2; //制定策略:下->右->上->左 if (setWay(map,i+1,j)){ return true; }else if (setWay(map,i,j+1)){ return true; }else if (setWay(map,i-1,j)){ return true; }else if (setWay(map,i,j-1)){ return true; }else { map[i][j] = 3; return false; } }else {//非0的情況可能是1、2、3,直接false return false; } } } }
結果: