[[392763]]

概念

簡(jiǎn)單地說:遞歸就是方法自己調(diào)用自己,每次調(diào)用時(shí)傳入不同的變量.遞歸有助于編程者解決復(fù)雜的問題,同時(shí)可以讓代碼變得整潔.

遞歸能解決什么樣的問題

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

遞歸需要遵守的規(guī)則

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

遞歸回溯解決迷宮問題

在一個(gè)二維數(shù)組中,1表示墻,求小球從指定點(diǎn)到終點(diǎn)走過的路徑.

package com.structures.recursion; 
 
public class MiGong { 
    public static void main(String[] args) { 
        //先創(chuàng)建二維數(shù)組模擬迷宮,地圖 
        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; 
        } 
        //設(shè)置擋板 
        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]位置,則說明通路找到 
     * 約定:當(dāng)map[i][j]為0表示該點(diǎn)沒有走過,當(dāng)為1表示墻,當(dāng)為2表示通路可以走,3表示該點(diǎn)已經(jīng)走過,但是走不通 
     * 在走迷宮時(shí),需要確定一個(gè)策略(方法),下->右->上->左,如果走不通再回溯 
     * 
     * @param map 表示地圖 
     * @param i   從哪個(gè)位置開始行坐標(biāo) 
     * @param j   從哪個(gè)位置開始列坐標(biāo) 
     * @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) {//如果當(dāng)前這個(gè)點(diǎn)沒有走過 
                //按照策略下->右->上->左 走 
                map[i][j] = 2;//假定該點(diǎn)可以走通 
                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;//說明該點(diǎn)是死路,走不通 
                    return false; 
                } 
            } else { 
                //如果map[i][j] != 0,說明可能是1,2,3 
                return false; 
            } 
        } 
    } 
} 

八皇后問題

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

理論上應(yīng)該創(chuàng)建一個(gè)二維數(shù)組來表示棋盤,但是實(shí)際上可以通過算法,用一個(gè)一維數(shù)組即可解決問題,arr[8]={0,4,7,5,2,6,1,3},對(duì)應(yīng)arr下標(biāo)表示第幾行,即第幾個(gè)皇后,arr[i]=val,val表示第i+1個(gè)皇后,放在第i+i行的val+1列.

package com.structures.recursion; 
 
public class Queen8 { 
    //表示共有多少個(gè)皇后 
    private int max = 8; 
    //定義數(shù)組array,保存皇后放置位置的結(jié)果,比如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個(gè)皇后 
    public void check(int n) { 
        if (n == max) {//n=8 說明前面已經(jīng)放好 
            print(); 
            count++; 
            return; 
        } 
        //依次放入皇后并判斷是否沖突 
        for (int i = 0; i < max; i++) { 
            //先把當(dāng)前的皇后n,放到改行的第1列 
            array[n] = i; 
            //判斷當(dāng)放置第n個(gè)皇后到第i列是,是否沖突. 
            if (judge(n)) { 
                //接著放n+1皇后,開始遞歸 
                check(n + 1); 
            } 
        } 
    } 
 
    //查看當(dāng)放置第n個(gè)皇后時(shí),就去檢測(cè)該皇后是否前面已經(jīng)擺放的皇后沖突 
    private boolean judge(int n) { 
        for (int i = 0; i < n; i++) { 
            //array[i] == array[n] 表示第n個(gè)皇后是否與之前的皇后在同一列 
            //Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示第n個(gè)皇后是否與之前在同一個(gè)斜線 
            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(); 
    } 
} 

 【編輯推薦】