遞歸的概念以及迷宮問題

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;
            }
        }
    }
}

　　結果：