遞歸
遞歸應用場景
看個實際應用場景诵原，迷宮問題(回溯)吹埠， 遞歸(Recursion)
image.png
遞歸的概念
簡單的說: 遞歸就是方法自己調(diào)用自己,每次調(diào)用時傳入不同的變量.遞歸有助于編程者解決復雜的問題,同時可以讓代碼變得簡潔植康。
遞歸調(diào)用機制
- 打印問題
/**
* 打印 1 ~ n
*
* @param num
*/
private static void testForEach(int num) {
if (num > 1) {
testForEach(num - 1);
}
System.out.println("num = " + num);
}
- 階乘問題
/**
* 階乘
* @param num
* @return
*/
public static int faction(int num) {
if (num == 1) {
return 1;
}
return faction(num - 1) * num;
}
- 使用圖解方式說明遞歸的調(diào)用機制
image.png
代碼演示
package com.www.recursion;
/**
* <p>
*
* @author Www
* <p>
* 郵箱： 483223455@qq.com
* <p>
* 創(chuàng)建時間: 2022/8/10 8:32 星期三
* <p>
*/
public class Demo {
/**
* 方法入口
*
* @param args 參數(shù)
*/
public static void main(String[] args) {
int num = 100;
testForEach(num);
int i = sumTest(100);
System.out.println(i);
int faction = faction(5);
System.out.println("faction = " + faction);
}
/**
* 打印 1 ~ n
*
* @param num
*/
private static void testForEach(int num) {
if (num > 1) {
testForEach(num - 1);
}
System.out.println("num = " + num);
}
/**
* 遞歸求和
*
* @param num
* @return
*/
public static int sumTest(int num) {
if (num == 1) {
return 1;
}
return sumTest(num - 1) + num;
}
/**
* 階乘
* @param num
* @return
*/
public static int faction(int num) {
if (num == 1) {
return 1;
}
return faction(num - 1) * num;
}
}
遞歸能解決什么問題
遞歸用于解決什么樣的問題
- 各種數(shù)學問題如:
* 8皇后問題 ,
* 漢諾塔,
* 階乘問題,
* 迷宮問題,
* 球和籃子的問題(google編程大賽) - 各種算法中也會使用到遞歸，
* 快排，
* 歸并排序，
* 二分查找庸毫，
* 分治算法等. - 將用棧解決的問題-->第歸代碼比較簡潔
遞歸需要遵守的重要規(guī)則
遞歸需要遵守的重要規(guī)則
- 執(zhí)行一個方法時，就創(chuàng)建一個新的受保護的獨立空間(椛婪空間)
- 方法的局部變量是獨立的飒赃，不會相互影響, 比如n變量
- 如果方法中使用的是引用類型變量(比如數(shù)組)，就會共享該引用類型的數(shù)據(jù).
- 遞歸必須向退出遞歸的條件逼近科侈，否則就是無限遞歸,出現(xiàn)StackOverflowError载佳，死龜了:)
- 當一個方法執(zhí)行完畢，或者遇到return臀栈，就會返回蔫慧，遵守誰調(diào)用，就將結(jié)果返回給誰挂脑，同時當方法執(zhí)行完畢或者返回時藕漱，該方法也就執(zhí)行完畢。
遞歸 - 迷宮 問題
迷宮問題
image.png
代碼實現(xiàn)
package com.www.recursion;
import java.util.Objects;
/**
* 遞歸 - 迷宮
* <p>
*
* @author Www
* <p>
* 郵箱： 483223455@qq.com
* <p>
* 創(chuàng)建時間: 2022/8/10 15:05 星期三
* <p>
*/
public class MiGong {
/**
* 方法入口
*
* @param args 參數(shù)
*/
public static void main(String[] args) {
// 先創(chuàng)建一個二維數(shù)組崭闲， 模擬迷宮 8 行 7 列
String[][] map = new String[8][7];
for (String[] ints : map) {
for (int j = 0; j < map[0].length; j++) {
ints[j] = "?";
}
}
// 使用 1 表示墻
// 第一行 和 第八行 是墻
for (int i = 0; i < 7; i++) {
map[0][i] = "??";
map[7][i] = "??";
}
// 第一列 和 第七列 是墻
for (int i = 0; i < 8; i++) {
map[i][0] = "??";
map[i][6] = "??";
}
// 擋板
map[3][1] = "??";
map[3][2] = "??";
/*map[2][5] = "??";
map[3][5] = "??";
map[4][5] = "??";
map[5][5] = "??";
map[5][3] = "??";*/
// map[6][5] = "??";
// 遍歷
for (String[] ints : map) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(ints[j] + "\t\t");
}
System.out.println();
}
setWap(map, 1, 1);
// 輸出新地圖
System.out.println("小球走過肋联。 并標識過的地圖的情況");
// 遍歷
for (String[] ints : map) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(ints[j] + "\t\t");
}
System.out.println();
}
}
/**
* 使用 遞歸回溯給小球找路
* <p>
* 如果小球能到 map[6][5] 位置， 則說明路通
* <p>
* 約定： 當 map[i][j] 為 ? 表示 該 點沒有走過 刁俭， 為 ?? 表示墻 橄仍， 為 ? 表示路可以走 ， 為 ? 表示該點已經(jīng)走過牍戚， 但是路不通
* <p>
* 在走迷宮的時候侮繁， 需要約定一個行走策略 （方法） 下 -> 右 -> 上 -> 左， 如果該點走不通如孝，再回溯
*
* @param map 迷宮地圖
* @param i 開始的位置 行值
* @param j 開始位置的 列值
* @return 路是否通
*/
public static boolean setWap(String[][] map, int i, int j) {
// 道路已找到宪哩，
if (Objects.equals(map[6][5], "?")) {
return true;
} else {
// 如果當前該點沒有走過
if (Objects.equals(map[i][j], "?")) {
// 按照策略 下 -> 右 -> 上 -> 左 走
// 假設該點是可以走通的
map[i][j] = "?";
// 向下走
if (setWap(map, i + 1, j)) {
return true;
// 向右走
} else if (setWap(map, i, j + 1)) {
return true;
// 向上走
} else if (setWap(map, i - 1, j)) {
return true;
// 向 左走
} else if (setWap(map, i, j - 1)) {
return true;
} else {
// 走不通
map[i][j] = "?";
return false;
}
} else { // 如果 map[i][j] !=0 可能是 1，2第晰，3
return false;
}
}
}
/**
* 使用 遞歸回溯給小球找路
* <p>
* 如果小球能到 map[6][5] 位置锁孟， 則說明路通
* <p>
* 約定： 當 map[i][j] 為 ? 表示 該 點沒有走過 ， 為 ?? 表示墻 茁瘦， 為 ? 表示路可以走 品抽， 為 ? 表示該點已經(jīng)走過， 但是路不通
* <p>
* 在走迷宮的時候甜熔， 需要約定一個行走策略 （方法） 上 -> 右 -> 上下-> 左圆恤， 如果該點走不通，再回溯
*
* @param map 迷宮地圖
* @param i 開始的位置 行值
* @param j 開始位置的 列值
* @return 路是否通
*/
public static boolean setWap2(String[][] map, int i, int j) {
// 道路已找到腔稀，
if (Objects.equals(map[6][5], "?")) {
return true;
} else {
// 如果當前該點沒有走過
if (Objects.equals(map[i][j], "?")) {
// 按照策略 下 -> 右 -> 上 -> 左 走
// 假設該點是可以走通的
map[i][j] = "?";
// 向上走
if (setWap(map, i - 1, j)) {
return true;
// 向右走
} else if (setWap(map, i, j + 1)) {
return true;
// 向下走
} else if (setWap(map, i + 1, j)) {
return true;
// 向 左走
} else if (setWap(map, i, j - 1)) {
return true;
} else {
// 走不通
map[i][j] = "?";
return false;
}
} else { // 如果 map[i][j] !=0 可能是 1盆昙，2，3
return false;
}
}
}
}
對迷宮問題的討論
- 小球得到的路徑 和程序員設置的找路策略有關(guān)： 找路的上下左右的順序相關(guān)
- 在得到小球路路徑時烧颖， 可以先使用 （上下左右）看看路徑是不是有變化
- 測試回溯現(xiàn)象
- 思考 ：如何求出最短路徑 弱左？ 思路 ---> 代碼實現(xiàn)
遞歸-八皇后問題(回溯算法)
八皇后問題介紹
八皇后問題，是一個古老而著名的問題炕淮，是回溯算法的典型案例拆火。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊涂圆，即：任意兩個皇后都不能處于同一行们镜、同一列或同一斜線上，問有多少種擺法润歉。
image.png
八皇后問題算法思路分析
- 第一個皇后先放第一行第一列
- 第二個皇后放在第二行第一列模狭、然后判斷是否OK， 如果不OK踩衩，繼續(xù)放在第二列嚼鹉、第三列贩汉、依次把所有列都放完，找到一個合適
- 繼續(xù)第三個皇后匹舞，還是第一列、第二列……直到第8個皇后也能放在一個不沖突的位置线脚，算是找到了一個正確解
- 當?shù)玫揭粋€正確解時赐稽，在椓闳纾回退到上一個棧時祸憋，就會開始回溯，即將第一個皇后肖卧，放到第一列的所有正確解蚯窥，全部得到.
- 然后回頭繼續(xù)第一個皇后放第二列，后面繼續(xù)循環(huán)執(zhí)行 1,2,3,4的步驟 【示意圖】
image.png
說明： 理論上應該創(chuàng)建一個二維數(shù)組來表示棋盤塞帐，但是實際上可以通過算法拦赠，用一個一維數(shù)組即可解決問題. arr = {0 , 4, 7, 5, 2, 6, 1, 3} //對應arr 下標 表示第幾行，即第幾個皇后葵姥，arr[i] = val , val 表示第i+1個皇后荷鼠，放在第i+1行的第val+1列
代碼實現(xiàn)
package com.www.recursion;
/**
* 八皇后問題
* <p>
*
* @author Www
* <p>
* 郵箱： 483223455@qq.com
* <p>
* 創(chuàng)建時間: 2022/8/10 16:50 星期三
* <p>
*/
public class EightQueens {
/**
* MAX 表示有多少個皇后
*/
private static final int MAX = 8;
/**
* 定義數(shù)組 array ，保存皇后位置的結(jié)果榔幸， 比如 array ={0,4,7,5,2,6,1,3}
*/
int[] array = new int[MAX];
/**
* 解法的個數(shù)
*/
static int count = 0;
/**
* 判斷的個數(shù)
*/
static int judgeCount = 0;
/**
* 方法入口
*
* @param args 參數(shù)
*/
public static void main(String[] args) {
EightQueens eightQueens = new EightQueens();
eightQueens.check(0);
System.out.printf("一共有 %d 解法", count);
System.out.printf("一共判斷沖突的次數(shù) %d 次", judgeCount);
}
/**
* 放置 第 n 個皇后
* <p>
* 特別注意： check 是每一次遞歸時允乐， 進入到 check 中都有 for( int i = 0; i < max ; i++ ), 因此會有 回溯
*
* @param n 第 n 個皇后
*/
private void check(int n) {
// n=8, 其實 8 個皇后已經(jīng)放好
if (n == MAX) {
// 打印
printQueens();
return;
}
// 依次放入皇后， 判斷是否沖突
for (int i = 0; i < MAX; i++) {
// 把當前皇后 n 削咆，放在該行的第 1 列
array[n] = i;
// 判斷當放置 第 n 個皇后到 i 列時牍疏， 是否沖突
if (judge(n)) {
// 不沖突
// 接著放 n + 1 個皇后， 即 將 第 n 個皇后拨齐，放置在 本行的 后移的一個位置
check(n + 1);
}
}
}
/**
* 在放置 第 n 個皇后的時候 去檢測該皇后是否和前面已經(jīng)擺放的皇后沖突
*
* @param n 表示 第 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 皇后是否在同一斜線
// 3.判斷是否在同一行， 【沒有必要】 n 每次都在 遞增
// 不滿足八皇后要求
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
/**
* 將皇后的擺放的位置輸出
*/
private void printQueens() {
for (int i : array) {
count++;
System.out.printf("%d\t", i);
}
System.out.println();
}
}
image.png
