遞歸的應(yīng)用場(chǎng)景

看個(gè)實(shí)際應(yīng)用場(chǎng)景，迷宮問題(回溯)， 遞歸(Recursion)

遞歸

遞歸的概念

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

我列舉兩個(gè)小案例,來幫助大家理解遞歸,給大家回顧一下遞歸調(diào)用機(jī)制
打印問題
階乘問題

public class RecTest {
    public static void main(String[] args) {
        test(5);
        int factorial = factorial(10);
        System.out.println(factorial);
    }

    //輸出什么?
    public static void test(int n) {
        if (n > 2) {
            test(n - 1);
        }
        System.out.println("n=" + n);
    }

    //階乘
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }
}

遞歸調(diào)用機(jī)制的圖解

遞歸能解決什么樣的問題

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

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

執(zhí)行一個(gè)方法時(shí)，就創(chuàng)建一個(gè)新的受保護(hù)的獨(dú)立空間(椪≡空間)
方法的局部變量是獨(dú)立的偷厦，不會(huì)相互影響, 比如n變量
如果方法中使用的是引用類型變量(比如數(shù)組)，就會(huì)共享該引用類型的數(shù)據(jù).
遞歸必須向退出遞歸的條件逼近燕刻，否則就是無限遞歸,出現(xiàn)StackOverflowError只泼，死龜了:)
當(dāng)一個(gè)方法執(zhí)行完畢，或者遇到return卵洗，就會(huì)返回请唱，遵守誰調(diào)用弥咪，就將結(jié)果返回給誰，同時(shí)當(dāng)方法執(zhí)行完畢或者返回時(shí)十绑，該方法也就執(zhí)行完畢聚至。

遞歸 - 迷宮問題

說明:
小球得到的路徑，和程序員?設(shè)置的找路策略有關(guān)即：找?路的上下左右的順序相關(guān)
再得到小球路徑時(shí)本橙，可以先?使用(下右上左)扳躬，再改成(上?右下左)，看看路徑是不是有變化
測(cè)試回溯現(xiàn)象
思考: 如何求出最短路徑?

代碼

package cn.icanci.datastructure.recursion;

import sun.util.resources.cldr.fr.CalendarData_fr_MQ;

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.datastructure.recursion
 * @Date: Created in 2020/3/3 21:28
 * @ClassAction: 迷宮問題
 */
public class MiGong {
    public static void main(String[] args) {
        //先創(chuàng)建一個(gè)二維數(shù)組,模擬迷宮
        //地圖
        int[][] map = new int[8][7];
        //使用1表示墻
        //上下為1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //左右為1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        //輸出地圖
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("==========================");
        //使用遞歸給小球找路
        setWay(map, 1, 1);
        //輸出新的地圖
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用遞歸回溯來給小球找路
     * 說明 出發(fā)點(diǎn)(1,1)
     * 如果到達(dá) (6,5) 說明找到
     * 約定 大概 map[i][j] 為0的時(shí)候,沒有走過 為1是墻 2為通路可走 3為已經(jīng)走過 但是走不通
     * 在走之前 需要確定一個(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) {
            //沒有走過
            //需要確定一個(gè)策略 (方法) 下->右->上->左 走不通 回溯
            //假定可以
            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;
        }
    }
}

打印

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 

最短路徑問題 全部思路都做一遍 然后找出最小得

遞歸 - 八皇后問題

八皇后問題介紹

八皇后問題甚亭，是一個(gè)古老而著名的問題贷币，是回溯算法的典型案例。該問題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后亏狰，使其不能互相攻擊役纹，即：任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上暇唾，問有多少種擺法促脉。

八皇后問題

八皇后問題算法思路分析

1.第一個(gè)皇后先放第一行第一列
2.第二個(gè)皇后放在第二行第一列、然后判斷是否OK策州， 如果不OK瘸味，繼續(xù)放在第二列、3.第三列够挂、依次把所有列都放完硫戈，找到一個(gè)合適
繼續(xù)第三個(gè)皇后，還是第一列下硕、第二列……直到第8個(gè)皇后也能放在一個(gè)不沖突的位置，算是找到了一個(gè)正確解
4.當(dāng)?shù)玫揭粋€(gè)正確解時(shí)汁胆，在椝笮眨回退到上一個(gè)棧時(shí)，就會(huì)開始回溯嫩码，即將第一個(gè)皇后誉尖，放到第一列的所有正確解，全部得到.
5.然后回頭繼續(xù)第一個(gè)皇后放第二列铸题，后面繼續(xù)循環(huán)執(zhí)行 1,2,3,4的步驟 【示意圖】

說明：理論上應(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+1行的第val+1列

代碼實(shí)現(xiàn)

package cn.icanci.datastructure.recursion;

/**
 * @Author: icanci
 * @ProjectName: AlgorithmAndDataStructure
 * @PackageName: cn.icanci.datastructure.recursion
 * @Date: Created in 2020/3/3 22:10
 * @ClassAction: 八皇后問題
 */
public class Queue8 {
    //定義一個(gè)max表示共有多少個(gè)皇后
    int max = 8;
    //定義數(shù)組array, 保存皇后放置位置的結(jié)果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {
        //測(cè)試一把 烘挫， 8皇后是否正確
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法", count);
        // 1.5w
        System.out.printf("一共判斷沖突的次數(shù)%d次", judgeCount);

    }



    //編寫一個(gè)方法诀艰，放置第n個(gè)皇后
    //特別注意： check 是 每一次遞歸時(shí)，進(jìn)入到check中都有  for(int i = 0; i < max; i++)，因此會(huì)有回溯
    private void check(int n) {
        //n = 8 , 其實(shí)8個(gè)皇后就既然放好
        if(n == max) {
            print();
            return;
        }

        //依次放入皇后其垄，并判斷是否沖突
        for(int i = 0; i < max; i++) {
            //先把當(dāng)前這個(gè)皇后 n , 放到該行的第1列
            array[n] = i;
            //判斷當(dāng)放置第n個(gè)皇后到i列時(shí)苛蒲，是否沖突
            // 不沖突
            if(judge(n)) {
                //接著放n+1個(gè)皇后,即開始遞歸
                check(n+1); 
            }
            //如果沖突，就繼續(xù)執(zhí)行 array[n] = i; 即將第n個(gè)皇后绿满，放置在本行得 后移的一個(gè)位置
        }
    }

    //查看當(dāng)我們放置第n個(gè)皇后, 就去檢測(cè)該皇后是否和前面已經(jīng)擺放的皇后沖突
    /**
     *
     * @param n 表示第n個(gè)皇后
     * @return
     */
    private boolean judge(int n) {
        judgeCount++;
        for(int i = 0; i < n; i++) {
            // 說明
            //1. array[i] == array[n]  表示判斷 第n個(gè)皇后是否和前面的n-1個(gè)皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判斷第n個(gè)皇后是否和第i皇后是否在同一斜線
            // n = 1  放置第 2列 1 n = 1 array[1] = 1
            // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
            //3. 判斷是否在同一行, 沒有必要臂外，n 每次都在遞增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
                return false;
            }
        }
        return true;
    }

    //寫一個(gè)方法，可以將皇后擺放的位置輸出
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

打印

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
2 4 1 7 5 3 6 0 
2 4 6 0 3 1 7 5 
2 4 7 3 0 6 1 5 
2 5 1 4 7 0 6 3 
2 5 1 6 0 3 7 4 
2 5 1 6 4 0 7 3 
2 5 3 0 7 4 6 1 
2 5 3 1 7 4 6 0 
2 5 7 0 3 6 4 1 
2 5 7 0 4 6 1 3 
2 5 7 1 3 0 6 4 
2 6 1 7 4 0 3 5 
2 6 1 7 5 3 0 4 
2 7 3 6 0 5 1 4 
3 0 4 7 1 6 2 5 
3 0 4 7 5 2 6 1 
3 1 4 7 5 0 2 6 
3 1 6 2 5 7 0 4 
3 1 6 2 5 7 4 0 
3 1 6 4 0 7 5 2 
3 1 7 4 6 0 2 5 
3 1 7 5 0 2 4 6 
3 5 0 4 1 7 2 6 
3 5 7 1 6 0 2 4 
3 5 7 2 0 6 4 1 
3 6 0 7 4 1 5 2 
3 6 2 7 1 4 0 5 
3 6 4 1 5 0 2 7 
3 6 4 2 0 5 7 1 
3 7 0 2 5 1 6 4 
3 7 0 4 6 1 5 2 
3 7 4 2 0 6 1 5 
4 0 3 5 7 1 6 2 
4 0 7 3 1 6 2 5 
4 0 7 5 2 6 1 3 
4 1 3 5 7 2 0 6 
4 1 3 6 2 7 5 0 
4 1 5 0 6 3 7 2 
4 1 7 0 3 6 2 5 
4 2 0 5 7 1 3 6 
4 2 0 6 1 7 5 3 
4 2 7 3 6 0 5 1 
4 6 0 2 7 5 3 1 
4 6 0 3 1 7 5 2 
4 6 1 3 7 0 2 5 
4 6 1 5 2 0 3 7 
4 6 1 5 2 0 7 3 
4 6 3 0 2 7 5 1 
4 7 3 0 2 5 1 6 
4 7 3 0 6 1 5 2 
5 0 4 1 7 2 6 3 
5 1 6 0 2 4 7 3 
5 1 6 0 3 7 4 2 
5 2 0 6 4 7 1 3 
5 2 0 7 3 1 6 4 
5 2 0 7 4 1 3 6 
5 2 4 6 0 3 1 7 
5 2 4 7 0 3 1 6 
5 2 6 1 3 7 0 4 
5 2 6 1 7 4 0 3 
5 2 6 3 0 7 1 4 
5 3 0 4 7 1 6 2 
5 3 1 7 4 6 0 2 
5 3 6 0 2 4 1 7 
5 3 6 0 7 1 4 2 
5 7 1 3 0 6 4 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 4 2 0 5 7 1 3 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
一共有92解法一共判斷沖突的次數(shù)15720次