數據結構之遞歸Demo（走迷宮）（八皇后）（漢諾塔）
遞歸
顧名思義，遞歸就是遞歸就是遞歸就是遞歸就是遞歸……就是遞歸
Google遞歸：😄
走迷宮（較容易）：
構建一個二維數組（如下圖），其中1表示圍牆，0表示通路，現要求從起點走到終點。利用遞歸可以以少量程式碼實現。
由於比較簡單，直接上程式碼分析：
參數 i，j 為迷宮起始坐標，而要走出迷宮，必須繞過圍牆1，走迷宮當然有策略，這裡比較簡單的給出了下右上左的次序判斷是否通路，同樣也可以上右下左，左上右下，左下右上，注意必須是閉環的，否則絕對走不出迷宮！（這裡強烈建議按照程式碼自己思考走一遍或者debug分析一下）
1 // 下右上左 2 public static boolean setWay(int[][] array, int i, int j) { 3 if (array[6][6] == 7)//判斷每一種選擇最後是否能走出迷宮 4 return true; 5 else { 6 if (array[i][j] == 0) { 7 array[i][j] = 7;//表示此坐標已經來過，下面接著判斷各種情況 8 if (setWay(array, i + 1, j)) 9 return true; 10 else if (setWay(array, i, j + 1)) 11 return true; 12 else if (setWay(array, i - 1, j)) 13 return true; 14 else if (setWay(array, i, j - 1)) 15 return true; 16 else { 17 array[i][j] = 3; 18 return false; 19 } 20 } else 21 return false; 22 } 23 }
八皇后：
八皇后小遊戲： //www.4399.com/baidugame/42643.htm 八皇后的規則很簡單，但是實現不易，八皇后規定每一個皇后都必須在不同行不同列且不在一個對角線上。
這裡給出92種擺法的一部分，感興趣的朋友可以點擊上面連接進行遊戲測試
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 public void check(int n) { 2 if (n == max) { 3 print(); 4 return; 5 } 6 for (int i = 0; i < max; i++) { 7 array[n] = i;// 這裡的i代表列，array[n]代表當前皇后放到第i列 8 if (judge(n)) {// 判斷當前皇后n是否滿足條件 9 check(n + 1);//滿足條件，判斷下一個皇后 10 } 11 } 12 } 13 14 //此方法主要判斷當前皇后能否擺放 15 public boolean judge(int n) { 16 for (int i = 0; i < n; i++) {// 此處i代表已經擺好的皇后序號，array[i]代表第i個皇后所在的列數, n代表當前的皇后，array[n]代表當前皇后所在的列數 17 //將當前第n個皇后的列array[n]和前n個皇后的列進行比較，還有斜率比較 18 if (array[n] == array[i] || Math.abs(n - i) == Math.abs(array[n] - array[i])) 19 return false; 20 } 21 return true; 22 }
漢諾塔（分治法）：
漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
假如按照上面規則去移動，一秒移動一次，那麼這表明移完這些金片需要5845.42億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。
為什麼呢？基本過程看圖：類似有規則的搭積木。
以上示圖分析，以3片為例，一共需要移動7次。
思路分析：將所有片看作兩部分，最底下一片和上面所有片；接著將上面所有片分為兩部分，最底下一片和上面所有片……
1、將所有上層片，從A放到B位置上
2、然後剩餘最底下的一片，從A放到C位置上
3、接著將B盤中所有片放到C位置上
以上是宏觀上的步驟，而真正移動是在回溯的時候。用圖說明一下：
方法在執行的時候是按照棧幀執行的，下面也就是模擬了一遍3片的執行過程。
1 //參數說明：num表示有多少片，abc依次表示三個容器 2 public static void hanoitower(int num,char a,char b,char c){ 3 if (num==1) 4 System.out.println("第1個盤從"+a+"->"+c);// 5 else { 6 //2個及多個盤子：第一步將其分成兩部分：最下面的和所有上層的； 7 hanoitower( num-1,a,c,b );//第一步將上層所有的盤子放到B位置，遞歸直到上層為1 8 System.out.println("第"+num+"個盤從"+a+"->"+c);//將所有相對於處於下層的盤子一個一個放到C 9 hanoitower( num-1,b,a,c );//將B中的所有盤子，放到C位置上，完成 10 } 11 }
