- 遞歸的概念
- 遞歸的調(diào)用機(jī)制
- 遞歸能解決的問題
- 遞歸需要遵守的重要規(guī)則
- 迷宮問題
- 八皇后問題
- 思路分析
- 代碼實(shí)現(xiàn)
1. 遞歸的概念
- 遞歸就是方法自己調(diào)用自己娶靡，每次調(diào)用時(shí) 傳入不同的變量
2. 遞歸的調(diào)用機(jī)制
image-20220324213825998
- 當(dāng)程序執(zhí)行到一個(gè)方法時(shí)，就會(huì)開辟一個(gè)獨(dú)立的空間（棧）
- 每個(gè)空間的數(shù)據(jù)（局部變量）,是獨(dú)立的轩拨。
3. 遞歸能解決的問題
- 8 皇后問題蛙紫、漢諾塔、階乘問題、迷宮問題捡需、球和籃子的問題
- 各種算法也會(huì)使用到，如 快排筹淫、歸并排序站辉、二分查找、分治算法等
4. 遞歸需要遵守的重要規(guī)則
- 執(zhí)行一個(gè)方法時(shí)损姜，就創(chuàng)建一個(gè)新的受保護(hù)的獨(dú)立空間（検伟空間）
- 方法的局部變量是獨(dú)立的，不會(huì)相互影響摧阅，比如：n 變量
- 如果方法中使用的是 引用類型變量汰蓉，就會(huì)共享該引用類型的數(shù)據(jù)
- 遞歸 必須向退出遞歸的條件逼近，否則就是無限遞歸棒卷，出現(xiàn)
StackOverflowError- 當(dāng)一個(gè)方法執(zhí)行完畢后顾孽，或者遇到 return祝钢，就會(huì)返回， 遵守誰調(diào)用若厚，就將結(jié)果返回結(jié)給誰拦英。
5. 迷宮問題
image-20220324214856337
-
思路分析
- 使用遞歸回溯來給小球找路
- 說明
- map 表示地圖
- i,j 表示從地圖的那個(gè)位置開始出發(fā)（1，1）
- 如果小球能到
map[6][5]位置测秸，則說明通路找到 - 約定：當(dāng) map[i][j] 為0疤估，表示該點(diǎn)沒有走過，當(dāng)為1表示墻乞封，2 表示通路可以軸做裙，3表示該點(diǎn)已經(jīng)走過，但是走不通
- 在走迷宮時(shí)肃晚，需要確定一個(gè)策略（方法）锚贱，下-》右-》上-》左，如果該點(diǎn)走不通关串，再回溯
代碼實(shí)現(xiàn)
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;
}
//設(shè)置擋板
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();
}
//使用遞歸回溯給小球找路
// setWay(map,1,1);
setWay2(map,1,1);
//輸出新的地圖，小球走過晋修，并標(biāo)識(shí)過的遞歸
//輸出地圖
System.out.println("小球走過邊標(biāo)識(shí)過的 地圖情況");
for(int i = 0; i < 8;i++){
for(int j = 0;j < 7;j++){
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
//使用遞歸回溯來給小球找路
//說明
//1. map 表示地圖
//2. i,j 表示從地圖的那個(gè)位置開始出發(fā)（1吧碾，1）
//3. 如果小球能到 map[6][5] 位置，則說明通路找到
//4. 約定：當(dāng) map[i][j] 為0墓卦，表示該點(diǎn)沒有走過倦春，當(dāng)為1表示墻，2 表示通路可以軸落剪，3表示該點(diǎn)已經(jīng)走過睁本，但是走不通
//5. 在走迷宮時(shí)，需要確定一個(gè)策略（方法）忠怖，下-》右-》上-》左呢堰，如果該點(diǎn)走不通，再回溯
/**
*
* @param map 表示地圖
* @param i 從那個(gè)位置開始找
* @param j
* @return 如果找到通路凡泣，就返回true枉疼，否則返回false
*/
public static boolean setWay(int[][] map,int i,int j){
if(map[6][5] == 2){ //通路已經(jīng)找到ok
return true;
}else{
if(map[i][j] == 0){ //如果當(dāng)前這個(gè)點(diǎn)沒有走過
//按照策略 下-》右-》上-》左
map[i][j] = 2; //假定該點(diǎn)是可以走通的
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 {
//說明該點(diǎn)走不通，是死路
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){ //通路已經(jīng)找到ok
return true;
}else{
if(map[i][j] == 0){ //如果當(dāng)前這個(gè)點(diǎn)沒有走過
//按照策略 下-》右-》上-》左
map[i][j] = 2; //假定該點(diǎn)是可以走通的
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 {
//說明該點(diǎn)走不通贺纲，是死路
map[i][j] = 3;
return false;
}
}else{ //如果 map[i][j]!=0,可能是1航闺，2，3
return false;
}
}
}
}
6. 八皇后問題
6.1 八皇后問題介紹
image-20220324215028098
- 在 8 X 8 格的國(guó)際象棋上擺八個(gè)皇后哮笆，使其不能互相攻擊来颤。即：任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上稠肘，問有多少中擺法
6.2 思路分析
- 第一個(gè)皇后先放到第一行第一列
- 第二個(gè)皇后放在第二行的第一列福铅，然后判斷是否 ok，繼續(xù)放在 第二列项阴、第三列滑黔、依次把所有列都放完，找到一個(gè)合適的
- 繼續(xù)第三個(gè)皇后环揽，還是第一列略荡，第二列， 直到第8個(gè)皇后也能放在一個(gè)不沖突的位置歉胶，算是找到了一個(gè)正確的解
- 當(dāng)?shù)玫搅艘粋€(gè)真確的解汛兜，在棧回退到上一個(gè)棧時(shí)通今，就會(huì)開始回溯粥谬，即將 第一個(gè)桓侯，放到第一列的所有正確解辫塌，全部得到漏策。
- 然后回頭繼續(xù)第一個(gè)皇后放到第二列，后面繼續(xù)循環(huán)執(zhí)行 1臼氨，2掺喻，3，4 的步驟储矩。
6.3 代碼實(shí)現(xiàn)
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;
public static void main(String[] args) {
//測(cè)試一把椰苟， 8皇后是否正確
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("一共有%d解法",count);
}
//編寫一個(gè)方法抑月，放置第n個(gè)皇后
//特別注意： check 是每一次遞歸時(shí)，進(jìn)入到 check 中都有 for(int i = 0; i < max; i++) 因此會(huì)有回溯
private void check(int n){
if(n == max){ //n = 8 舆蝴，其實(shí)8個(gè)皇后已經(jīng)放好
print();
return;
}
//依次放入皇后谦絮，并判斷是否沖突
for(int i = 0; i < max;i++){
//先把當(dāng)前這個(gè)皇后 n ,放到該行的第一列
array[n] = i;
//判斷當(dāng)放置第 n 個(gè)皇后到第 i 列時(shí)，是否沖突
if(judge(n)){ //不沖突
//接著放 n+1 個(gè)皇后洁仗，即開始遞歸
check(n+1); //回溯层皱，每次都有for循環(huán)
}
//如果沖突，就繼續(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){
for (int i = 0; i < n; i++) {
//說明
//1.arr[i] == array[n] 表示判斷第n個(gè)皇后是否與前 n-1 個(gè)同列
//2.Math.abs(n-i) == Math.abs(array[n]-array[i]) 判斷是否在同一斜線上 （利用數(shù)學(xué)的坐標(biāo)法叫胖，判斷是否在同一斜線，
// abs(橫坐標(biāo)-橫坐標(biāo)) == abs(縱坐標(biāo) - 縱坐標(biāo))
//3.判斷是否在同一行她奥，沒有必要瓮增，因?yàn)?n 每次循環(huá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();
}
}
