[[392763]]

概念

簡單地說:遞歸就是方法自己調用自己,每次調用時傳入不同的變量.遞歸有助于編程者解決復雜的問題,同時可以讓代碼變得整潔.

遞歸能解決什么樣的問題

1. 各種數學問題如:八皇后問題,漢諾塔,階乘問題,迷宮問題,球和籃子問題(google編程大賽).
2. 各種算法中也會用到遞歸,比如快排,歸并排序,二分查找,分治算法等.
3. 將用棧解決的問題->遞歸代碼比較簡潔.

遞歸需要遵守的規則

1. 執行一個方法時,就創建一個新的受保護的獨立空間(棧空間).
2. 方法的局部變量是獨立的,不會相互影響.
3. 如果方法中使用的變量是引用類型的變量(比如數組),就會共享該引用類型的數據.
4. 遞歸必須向退出遞歸的條件逼近,否則就是無限遞歸.
5. 當一個方法執行完畢,或者遇到return,就會返回,遵守誰調用就將結果返回給誰,同時當方法執行完畢或者返回時,該方法也就執行完畢.

遞歸回溯解決迷宮問題

在一個二維數組中,1表示墻,求小球從指定點到終點走過的路徑.

package com.structures.recursion; 
 
public class MiGong { 
    public static void main(String[] args) { 
        //先創建二維數組模擬迷宮,地圖 
        int[][] map = new int[8][7]; 
        //使用1表示墻,迷宮的上下左右邊全部置為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 < 8; i++) { 
            for (int j = 0; j < 7; j++) { 
                System.out.print(map[i][j] + " "); 
            } 
            System.out.println(); 
        } 
 
        //使用遞歸回溯找路 
        setWay(map, 1, 1); 
        System.out.println("按策略走過的路"); 
        for (int i = 0; i < 8; i++) { 
            for (int j = 0; j < 7; j++) { 
                System.out.print(map[i][j] + " "); 
            } 
            System.out.println(); 
        } 
 
        /* 
        原始地圖 
        1 1 1 1 1 1 1 
        1 0 0 0 0 0 1 
        1 0 0 0 0 0 1 
        1 1 1 0 0 0 1 
        1 0 0 0 0 0 1 
        1 0 0 0 0 0 1 
        1 0 0 0 0 0 1 
        1 1 1 1 1 1 1 
        按策略走過的路 
        1 1 1 1 1 1 1 
        1 2 0 0 0 0 1 
        1 2 2 2 0 0 1 
        1 1 1 2 0 0 1 
        1 0 0 2 0 0 1 
        1 0 0 2 0 0 1 
        1 0 0 2 2 2 1 
        1 1 1 1 1 1 1 
         */ 
    } 
 
    /** 
     * 使用遞歸回溯來找路,如果能map[6][5]位置,則說明通路找到 
     * 約定:當map[i][j]為0表示該點沒有走過,當為1表示墻,當為2表示通路可以走,3表示該點已經走過,但是走不通 
     * 在走迷宮時,需要確定一個策略(方法),下->右->上->左,如果走不通再回溯 
     * 
     * @param map 表示地圖 
     * @param i   從哪個位置開始行坐標 
     * @param j   從哪個位置開始列坐標 
     * @return 如果找到通路, 就返回true, 否則返回false 
     */ 
    public static boolean setWay(int[][] map, int i, int j) { 
        if (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 { 
                //如果map[i][j] != 0,說明可能是1,2,3 
                return false; 
            } 
        } 
    } 
} 

八皇后問題

在8*8的國際象棋上擺放8個皇后,使其不能相互攻擊,即:任意兩個皇后都不能處于同一行,同一列,同一斜線上,問有多少種擺法.

理論上應該創建一個二維數組來表示棋盤,但是實際上可以通過算法,用一個一維數組即可解決問題,arr[8]={0,4,7,5,2,6,1,3},對應arr下標表示第幾行,即第幾個皇后,arr[i]=val,val表示第i+1個皇后,放在第i+i行的val+1列.

package com.structures.recursion; 
 
public class Queen8 { 
    //表示共有多少個皇后 
    private int max = 8; 
    //定義數組array,保存皇后放置位置的結果,比如arr[8]={0,4,7,5,2,6,1,3} 
    private int[] array = new int[max]; 
 
    static int count = 0; 
 
    public static void main(String[] args) { 
        Queen8 queen8 = new Queen8(); 
        queen8.check(0); 
        System.out.printf("總共%d擺法\n",count);//92種 
    } 
 
    //放置第n個皇后 
    public void check(int n) { 
        if (n == max) {//n=8 說明前面已經放好 
            print(); 
            count++; 
            return; 
        } 
        //依次放入皇后并判斷是否沖突 
        for (int i = 0; i < max; i++) { 
            //先把當前的皇后n,放到改行的第1列 
            array[n] = i; 
            //判斷當放置第n個皇后到第i列是,是否沖突. 
            if (judge(n)) { 
                //接著放n+1皇后,開始遞歸 
                check(n + 1); 
            } 
        } 
    } 
 
    //查看當放置第n個皇后時,就去檢測該皇后是否前面已經擺放的皇后沖突 
    private boolean judge(int n) { 
        for (int i = 0; i < n; i++) { 
            //array[i] == array[n] 表示第n個皇后是否與之前的皇后在同一列 
            //Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示第n個皇后是否與之前在同一個斜線 
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { 
                return false; 
            } 
        } 
        return true; 
    } 
 
    //將皇后擺放的位置輸出 
    public void print() { 
        for (int i = 0; i < array.length; i++) { 
            System.out.print(array[i] + " "); 
        } 
        System.out.println(); 
    } 
} 

 【編輯推薦】