第 6 章 遞歸
1 遞歸的應用場景
看個實際應用場景，迷宮問題(回溯)， 遞歸
(Recursion
)
2 遞歸的概念
遞歸就是方法自己調用自己,每次調用時傳入不同的變量.遞歸有助于程式設計者解決複雜的問題,同時可以讓代碼變得簡潔。
3 遞歸需要遵守的重要規則
- 執行一個方法時，就建立一個新的受保護的獨立空間(棧空間)
- 方法的局部變量是獨立的，不會互相影響, 比如n變量
- 如果方法中使用的是引用類型變量(比如數組)，就會共享該引用類型的資料.
- 遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸,出現StackOverflowError，死龜了:)
- 當一個方法執行完畢，或者遇到return，就會傳回，遵守誰調用，就将結果傳回給誰，同時當方法執行完畢或者傳回時，該方法也就執行完畢。
4 遞歸能解決什麼樣的問題
- 各種數學問題如: 8皇後問題 , 漢諾塔, 階乘問題, 迷宮問題, 球和籃子的問題(google程式設計大賽)
- 各種算法中也會使用到遞歸，比如快排，歸并排序，二分查找，分治算法等.
- 将用棧解決的問題–>遞歸代碼比較簡潔
5 遞歸小執行個體
public class RecursionTest {
public static void main(String[] args) {
//通過列印問題， 回顧遞歸問題
// test(4);
int res = factorial(1);
System.out.println("res:" + res);
}
public static void test(int n) {
if (n > 2) {
test(n - 1);
} else {
System.out.println("n=" + n);
}
}
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
}
6 迷宮問題
說明:
- 小球得到的路徑，和程式員設定的找路政策有關即：找路的上下左右的順序相關
- 再得到小球路徑時，可以先使用(下右上左)，再改成(上右下左)，看看路徑是不是有變化
-
測試回溯現象
思考: 如何求出最短路徑?
6.1 迷宮問題代碼實作
public class MiGong {
public static void main(String[] args) {
//先建立一個二維數組
// 1. 在建立一個地圖
int[][] map = new int[8][7];
// 1.1 使用1作為牆
for (int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
//1.1.1 左右全為1
for (int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
// 1.2 設定擋闆
map[3][1] = 1;
map[3][2] = 1;
//再測試:
// map[1][2] = 1;
// map[2][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);
//改變政策， 再使用遞歸
setWay2(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();
}
}
//使用遞歸來給小球找路
//tip:
/*
1. map 表示地圖
2. i，j 表示從地圖的那個位置開始出發(1, 1)
3. 如果小球能到 map[6][5] 位置， 則說明路找到
4. 約定map[i][j] 為0 表示該點沒有走過，1：為牆， 2：可以走， 3： 已經走過了
5. 在走迷宮時， 需要确定一個政策， 下 -> 右 -> 上 -> 左
6. 如果走不通， 再回溯
*/
/**
* @param map 表示地圖
* @param i 從哪個地方找
* @param j
* @return if can find way return true, else return 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;
}
}
}
//修改政策， 改為： 上-> 右 -> 下 -> 左
public static boolean setWay2(int[][] map, int i, int j) {
if (map[6][5] == 2) {//路已經找到
return true;
} else {
if (map[i][j] == 0) {//如果如果單前這個點還沒有走過，按照政策繼續走
map[i][j] = 2;
if (setWay2(map, i - 1, j)) {//向上走
return true;
} else if (setWay2(map, i, j + 1)) {//向右走
return true;
} else if (setWay2(map, i + 1, j)) {//向下走
return true;
} else if (setWay2(map, i, j - 1)) {
return true;
} else {
//說明這個是死路，走不通
map[i][j] = 3;
return false;
}
} else { //如果map[i][j] != 0, 可能是 1， 2 ，3
return false;
}
}
}
}
7 八皇後問題
八皇後問題介紹：
八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在
8×8
格的國際象棋上擺放八個皇後，使其不能互相攻擊，即：任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法？
7.1 八皇後代碼實作
package itcast03;
public class Queue8 {
//定義一個max表示共有多少個皇後
int max = 8;
//定義一個數組array， 儲存皇後放置的位置的結果， 比如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) {
//測試一把， 8皇後是否正确
Queue8 queue8 = new Queue8();
queue8.check(0);//先放第一個皇後
System.out.println("一共有" + count + "種解法。");
System.out.println("一共進行了" + judgeCount + "次判斷。");
}
//編寫一個方法， 放置第n個皇後
//特别注意： check 是每一次遞歸時， 進入check 中都有 for(int i = 0; i < max; i++)
private void check(int n) {
if (n == max) {//n = 8, 其實8個皇後就已經放好
print();
return;
}
//依次放入皇後， 并判斷是否沖突
for (int i = 0; i < max; i++) {
//依次放入皇後n, 放到該行的第1列
array[n] = i;
//判斷當放置第n個皇後到i列時， 是否沖突
if (judge(n)) {//不沖突
//接着放 n+1 個皇後， 開始遞歸
check(n + 1);
}
//如果沖突， 就繼續執行array[n] = i; 即将第n個皇後， 放置在本行的 後移一個的位置
}
}
//檢視當我們放置第 n 個皇後， 就去檢測該皇後是否和前面已經擺放的皇後沖突
/**
* @param n 表示第幾個皇後
* @return true 表示可以， false 表示不可以
*/
private boolean judge(int n) {
judgeCount++;
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 個 是否 和 第 i 個皇後在同一斜線上
n = 1 放置在第二列 n = 1， array[1] = 1
Math.abs(1 - 0) == 1 Math.abs(array[n] - array[i]) == 1
3. 判斷是否同一行， 沒有必要， n 每次都在遞增
*/
/*
理論上應該建立一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題.
arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}
對應arr 下标 表示第幾行，即第幾個皇後，arr[i] = val , val 表示第i+1個皇後，放在第i+1行的第val+1列
*/
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
//寫一個方法，可以将皇後擺放的位置輸出
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)