# 遞迴(Recursion)

遞迴就是一個函式直接或間接的呼叫自己本身，用相同的方法解決重複性的問題，有助於programmer解決複雜的問題，同時可以讓代碼變得簡潔。

**應用場景**：迷宮

舉兩個小案例來幫助大家理解或複習遞迴：
## 遞迴案例

我們用打印問題和階乘問題來講解遞迴的調用機制。

### 打印問題

請問下方程式碼的輸出結果為何?

public class RecursionDemo {
    public static void main(String[] args) {
        test(6);
    }

    public static void test(int n) {
        if (n > 2) {
            test(n-1);
        }
        System.out.println("n = "+n);
    }
}

答案是

n = 2
n = 3
n = 4

### 階乘問題

請大家思考一下，下方程式碼會輸出什麼呢？

public class RecursionDemo {
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

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

調用 factorial(4) 的步驟為

...
return factorial(4 - 1)*4; //*4

這邊調用了 factorial(3) 所以我們還需要再去做 factorial(3)

...
return factorial(3 - 1)*3; //3*4

做 factorial(2)

return factorial(2 - 1)*2; //*2*3*4

做 factorial(1)

return 1; //1*2*3*4

最後得出結果 4! = `24`

## 遞迴調用規則
1. 當程序執行到一個方法時，就會開闢一個獨立的空間(棧)
2. 每個空間的數據(局部變數)是獨立的。
3. 如果方法中使用的是引用類型變數(比如陣列)，就會共享該引用類型的數據，即每個棧用的數據指向同一份數據空間
4. 遞迴必須向退出遞迴的條件逼近，否則就是無限遞迴 **StackOverfloweError(棧溢出)**
5. 當一個方法執行完畢後，或者遇到return，就會返回，遵守誰調用就將結果返回誰，同時當方法執行完畢或者返回時，該方法也就執行完畢。

**示意圖**

**Q：若將打印問題的程式碼改為下方程式碼，請問會輸出什麼呢?**

public static void test(int n) {
    if (n > 2) {
        test(n-1);
    } else {
        System.out.println("n = "+n);
    }
}

A：只會輸出 `n = 2` 而已。

## 遞迴能解決什麼問題?
1. 各種數學問題如：八皇后問題、河內塔、階乘問題、迷宮問題、球和籃子的問題
2. 各種演算法中也會使用到遞迴，比如：快速排序法、合併排序法、二分搜尋法、分治法...等。
3. 將用棧解決的問題改為遞迴，程式碼會比較簡潔。

## 迷宮回溯問題分析和實現

**說明**：
1. 小球得到的路徑和programmer設置的找路策略有關
2. 在得到小球路徑時，可以先使用(下右上左)，再改成(上右下左)，看看路徑是不是有變化？
3. 測試回溯現象
4. 思考：如何求出最短路徑？

核心程式碼：

/** 使用遞迴回溯來給小球找路
 * 說明:
 * 1. map 表示地圖
 * 2. i,j 表示從地圖的哪個位置開始出發
 * 3. 如果小球能到 map[6][5]位置,則說明通路找到
 * 4. 約定: 當map[i][j] 為 0 表示該點沒有走過, 當為1 表示牆, 2表示可以走, 3表示該位置已經走過但是走不通
 * 5. 在走迷宮時,需要確定一個策略,下->右->上->左,如果該點走不通再回溯*/

/**
 * @param map 表示地圖
 * @param i 從哪個位置開始找
 * @param j
 * @return 如果找到通路就返回true,否則返回false
 */
public boolean setWay(int i, int j) {
    if(map[row-2][col-2] == 2){ //通路已經找到
        return true;
    } else {
        if(map[i][j] == 0) { //當前點還沒走過
            //按照策略 下->右->上->左 走
            map[i][j] = 2; //假定該點能走通

            if(setWay(i+1 ,j )) { //向下走
                return true;
            } else if(setWay(i ,j+1 )) { //向右走
                return true;
            } else if(setWay(i-1 ,j )) { //向上走
                return true;
            } else if(setWay(i ,j-1 )) { //向左走
                return true;
            } else {
                // 說明該點是走不通,是死路
                map[i][j] = 3;
                return false;
            }
        } else { // 如果map[i][j] != 0,可能是 1,2,3
            return false;
        }
    }
}

### 程式碼

這部分我是沒有按照老師的去寫，僅學習了思路，老師寫的是寫死的迷宮大小和檔板，我自己改寫了可以設置迷宮大小和亂數產生檔板的迷宮，程式碼在下方，寫得很垃圾僅供參考。

import java.util.Scanner;

public class MiGong {
    public static void main(String[] args) {   
        Map map = new Map();
        map.BuildMap();
        map.ShowMap();

        //使用遞迴給小球找路
        System.out.println("輸出新的地圖,小球走過並標示的遞迴");
        map.setWay(1, 1);
        map.ShowMap();
    }
}

class Map{
    private int[][] map;
    private int row,col;
    private int[] gateRow = new int[8];
    private int[] gateCol = new int[8];
    private int n,m;

    //地圖產生
    public void BuildMap() {
        Scanner sc = new Scanner(System.in);
        System.out.print("輸入列數：");
        row = sc.nextInt();
        System.out.print("輸入行數：");
        col = sc.nextInt();
        sc.close();
        map = new int[row][col];

        if(row < col) {
            m = row;
        } else {
            m = col;
        }

        //檔板產生
        for(int i=0; i < m-3 ; i++) {        
            do{
                n = (int)(Math.random() * row - 1);
                gateRow[i] = n;
                n = (int)(Math.random() * col - 1);
                gateCol[i] = n;
            } while(gateRow[i] == 0 || gateCol[i] == 0 || gateRow[i] == row || gateCol[i] == col || (gateRow[i] == 1 && gateCol[i] == 1)  || (gateRow[i] == row-2 && gateCol[i] == col-2));
        }

        //使用 1 表示牆
        //上下皆為牆(第一列和最後一列)全部設置為 1
        for(int i=0; i < col; i++) {
            map[0][i] = 1;
            map[col-1][i] = 1;
        }

        //左右皆為牆(第一行和最後一行)全部設置為 1
        for(int i=1; i < row-1; i++) {
            map[i][0] = 1;
            map[i][row-1] = 1;
        }

        //檔板
        for(int i=0; i < m-3 ; i++) {
            map[gateRow[i]][gateCol[i]] = 1;
        } 
    }

    //輸出地圖
    public void ShowMap() {    
        for(int i=0;i < row;i++) {
            for(int j=0;j < col;j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }

    /** 使用遞迴回溯來給小球找路
     * 說明:
     * 1. map 表示地圖
     * 2. i,j 表示從地圖的哪個位置開始出發
     * 3. 如果小球能到 map[6][5]位置,則說明通路找到
     * 4. 約定: 當map[i][j] 為 0 表示該點沒有走過, 當為1 表示牆, 2表示可以走, 3表示該位置已經走過但是走不通
     * 5. 在走迷宮時,需要確定一個策略,下->右->上->左,如果該點走不通再回溯*/

    /**
     * @param map 表示地圖
     * @param i 從哪個位置開始找
     * @param j
     * @return 如果找到通路就返回true,否則返回false
     */
    public boolean setWay(int i, int j) {
        if(map[row-2][col-2] == 2){ //通路已經找到
            return true;
        } else {
            if(map[i][j] == 0) { //當前點還沒走過
                //按照策略 下->右->上->左 走
                map[i][j] = 2; //假定該點能走通

                if(setWay(i+1 ,j )) { //向下走
                    return true;
                } else if(setWay(i ,j+1 )) { //向右走
                    return true;
                } else if(setWay(i-1 ,j )) { //向上走
                    return true;
                } else if(setWay(i ,j-1 )) { //向左走
                    return true;
                } else {
                    // 說明該點是走不通,是死路
                    map[i][j] = 3;
                    return false;
                }
            } else { // 如果map[i][j] != 0,可能是 1,2,3
                return false;
            }
        }
    }
    
}


0為可以走的路，1為牆，2為走的路線，3為走過但走不通的路。

上方結果可以看到小球嘗試要從(2,1)走到(3,1)，但是因為(3,1)是牆無法走所以又往上走回去找別的路，所以(3,1)是 3。

這個code BUG還是不少，不過只是先理解遞迴實現走迷宮的概念。

### 如何尋找最短路徑?

在還沒學習更好的演算法之前，我們可以透過更改找路的策略來找出最短路徑，比如：用一個陣列表示不同的策略，for循環把幾個策略走一遍，將這些策略走的 2 個數存在一個集合中，看哪個集合小便採用那個策略。

就像我們可以把找路策略從 下->右->上->左 改為 上->右->下->左，將兩個策略走過的路個數拿來比較，看看哪個走的路比較少便保存起來，多比對幾個找路策略所走的路找出最短路徑。

## 八皇后問題分析和實現

八皇后問題是一個古老而著名的問題，是回溯演算法的典型案例。該問題是國際西洋棋手馬克思於1848年提出：在8*8格的國際象棋上擺放八個皇后，使其不能互相攻擊。

### 規則
西洋棋中的皇后可以攻擊棋盤上**同行、同列、同對角線**的位置，所以要如何在 8*8 棋盤上擺放八個皇后並且每個皇后不會攻擊到彼此是一個需要去思考的問題。

總的來說，就是每個皇后的同行、同列、同對角線不能有別的皇后。

[八皇后小遊戲](https://www.novelgames.com/zh-HK/queens/)


### 思路分析
1. 第一個皇后先放在第一行第一列。
2. 第二個皇后放在第二行第一列，判斷是否成立，若不成立繼續放在第二列、第三列..依次把所有列放完，找到一個合適的位置。
3. 繼續第三個皇后，還是第一列、第二列、第三列..直到第八個皇后也能放在一個不衝突的位置即為正解。
4. 當得到一個正解時，在棧回退到上一個棧時，就會開始回溯，即將第一個皇后放到第一列的所有正解全部得到。
5. 然後回頭繼續第一個皇后放第二列，後面繼續循環執行1,2,3,4的步驟。


想知道每個解的擺法可以看[維基百科](https://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98)。

### 說明
理論上應該創建一個二維陣列來表示棋盤，但其實可以通過演算法，用一個一維陣列即可解決問題。

// 對應arr：index表示列、值表示行；
// arr[i] = val , val 表示第i+1個皇后 放在第i+1列的 第val+1行
arr[8] = {0, 4, 7, 5, 2, 6, 1, 3} 

比如說這個一維陣列指的就是：

* 第一個皇后擺在第一列第一行(0+1)
* 第二個皇后擺在第二列第五行(4+1)
* 第三個皇后擺在第三列第八行(7+1)
* 第四個皇后擺在第四列第六行(5+1)

..以此類推

### 程式碼實現

首先，我們需要先宣告 皇后個數和保存皇后放置位置結果的陣列。

int max = 8; //共有多少個皇后
int [] array = new int[max]; //保存皇后放置位置的結果

寫一個方法，用於判斷當前放置的皇后和前面已經擺放的皇后是否有衝突。

//查看當我們放置第n個皇后, 就去檢測該皇后是否和前面已擺放的皇后衝突
/**
 * 
 * @param n 表示第n個皇后
 * @return
 */
private boolean judgePosition(int n) {
    for(int i = 0; i < n; i++) {
        //1. array[i] == array[n] 判斷第n個皇后是否和前面的n-1個皇后在同一列
        //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 判斷第n個皇后是否和前面n-1個皇后在同一對角線
        //第二個皇后 n = 1 , 假設放在第二行{0,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;
}

接著寫一個方法來實際放置皇后，並且放置過程中需要使用到`judgePosition`方法來判斷這個皇后是否和之前放置的皇后有衝突，如果衝突便繼續放置下一行試試，如果沒有衝突則可以繼續放置下一個皇后。

//方法:放置第n個皇后
//特別注意: checkPostion 每一次遞迴時進入到 checkPostion 中
//都有 for(int i = 0; i < max; i++), 因此會有回溯

private void checkPostion(int n) {
    if(n == max) {
        printPosition();
        return;
    }

    //依次放入皇后 並判斷是否衝突
    for(int i = 0; i < max; i++) {
        //先把當前這個皇后放到該列的第一行
        array[n] = i;
        //判斷當放置第n個皇后到i行時是否衝突
        if(judgePosition(n)) { //不衝突
            //接著放 n+1個皇后, 即開始遞迴
            checkPostion(n+1);
        }

        //如果衝突,就繼續執行 array[n] = i; 並且i+1
    }
}

最後，寫一個方法將擺放結果輸出

//將皇后擺放位置輸出
private void printPosition() {
    count++;
    for(int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

**完整程式碼**

public class EightQueen {
    int max = 8; //共有多少個皇后
    int [] array = new int[max]; //保存皇后放置位置的結果
    static int count;
    public static void main(String[] args) {
        EightQueen EightQueen = new EightQueen();
        EightQueen.checkPostion(0);
        System.out.printf("一共有 %d 種解法",count);
    }

    //方法:放置第n個皇后
    //特別注意: checkPostion 每一次遞迴時進入到 checkPostion 中都有 for(int i = 0; i < max; i++), 因此會有回溯
    private void checkPostion(int n) {
        if(n == max) {
            printPosition();
            return;
        }

        //依次放入皇后 並判斷是否衝突
        for(int i = 0; i < max; i++) {
            //先把當前這個皇后放到該列的第一行
            array[n] = i;
            //判斷當放置第n個皇后到i行時是否衝突
            if(judgePosition(n)) { //不衝突
                //接著放 n+1個皇后, 即開始遞迴
                checkPostion(n+1);
            }

            //如果衝突,就繼續執行 array[n] = i; 並且i+1
        }
    }

    //查看當我們放置第n個皇后, 就去檢測該皇后是否和前面已擺放的皇后衝突
    /**
     * 
     * @param n 表示第n個皇后
     * @return
     */
    private boolean judgePosition(int n) {
        for(int i = 0; i < n; i++) {
            //1. array[i] == array[n] 判斷第n個皇后是否和前面的n-1個皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 判斷第n個皇后是否和前面n-1個皇后在同一對角線
            //第二個皇后 n = 1 , 假設放在第二行{0,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;
    }

    //將皇后擺放位置輸出
    private void printPosition() {
        count++;
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}