溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“Java如何實現遞歸算法”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“Java如何實現遞歸算法”這篇文章吧。
遞歸：遞歸就是方法自己調用自己，每次調用時傳入不同的變量。遞歸有助于編程者解決復雜的問題，同時可以讓代碼變得簡潔。
迭代和遞歸區別：迭代使用的是循環結構，遞歸使用的選擇結構。使用遞歸能使程序的結構更清晰、更簡潔、更容易讓人理解，從而減少讀懂代碼的時間。其時間復雜度就是遞歸的次數。
但大量的遞歸調用會建立函數的副本，會消耗大量的時間和內存，而迭代則不需要此種付出。
遞歸函數分為調用和回退階段，遞歸的回退順序是它調用順序的逆序。
分治：當一個問題規模較大且不易求解的時候，就可以考慮將問題分成幾個小的模塊，逐一解決。
兔子繁殖的問題。（斐波那契數列）。
計算 n! 。
任意長度的字符串反向輸出。
折半查找算法的遞歸實現。
漢諾塔問題
八皇后問題
問題：尋找一條從起始點到達終點的有效路徑。
代碼示例：迷宮
public class MiGong {
/**
* 0:該點沒有走過, 1:表示墻, 2:可以走, 3:該點已經走過,但是走不通\
* 策略: 下->右->上->左, 如果該點走不通，再回溯
*/
private int[][] map;
private int desX;
private int desY;
/**
* 構建 row*col的迷宮
*
* @param row 行
* @param col 列
*/
public MiGong(int row, int col) {
if (row <= 0 || col <= 0) {
return;
}
map = new int[row][col];
// 默認 上下左右 全部為墻
for (int i = 0; i < col; i++) {
map[0][i] = 1;
map[row - 1][i] = 1;
}
for (int i = 0; i < row; i++) {
map[i][0] = 1;
map[i][col - 1] = 1;
}
}
/**
* 在迷宮內部添加擋板
*
* @param i 橫坐標
* @param j 縱坐標
*/
public void addBaffle(int i, int j) {
if (map == null) {
return;
}
// 外面一周都是墻
if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
map[i][j] = 1;
}
}
/**
* 設置迷宮的終點位置
*
* @param desX 橫坐標
* @param desY 縱坐標
*/
public void setDes(int desX, int desY) {
this.desX = desX;
this.desY = desY;
}
public boolean setWay(int i, int j) {
// 通路已經找到
if (map[desX][desY] == 2) {
return true;
} else {
if (map[i][j] != 0) {
return false;
}
// 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;
}
}
}
// 顯示地圖
public void show() {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}代碼示例：測試類
// 測試類
public class Main {
public static void main(String[] args) {
MiGong miGong = new MiGong(8, 7);
miGong.addBaffle(3, 1);
miGong.addBaffle(3, 2);
miGong.setDes(6, 5); // 設置目的地
System.out.println("初始地圖的情況");
miGong.show();
miGong.setWay(1, 1); // 設置起始位置
System.out.println("小球走過的路徑,地圖的情況");
miGong.show();
}
}// 結果
初始地圖的情況
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
小球走過的路徑,地圖的情況
1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1
問題：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即：任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
代碼示例：八皇后
public class Queue8 {
private static final int MAX = 8;
// 保存皇后放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
private final int[] array = new int[MAX];
public static int count = 0;
public static int judgeCount = 0;
public void check() {
this.check(0);
}
// check 是每一次遞歸時，進入到check中都有 for(int i = 0; i < max; i++)，因此會有回溯
private void check(int n) {
// n = 8, 表示8個皇后就已經放好
if (n == MAX) {
print();
return;
}
for (int i = 0; i < MAX; i++) {
array[n] = i;
// 判斷當放置第n個皇后到i列時，是否沖突
// 不沖突
if (!judge(n)) {
// 接著放n+1個皇后,即開始遞歸
check(n + 1);
}
}
}
private boolean judge(int n) {
judgeCount++;
for (int i = 0; i < n; i++) {
// 同一列 或 同一斜線
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return true;
}
}
return false;
}
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}代碼示例：測試類
// 測試類
public class Main {
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check();
System.out.printf("一共有%d解法", Queue8.count);
System.out.printf("一共判斷沖突的次數%d次", Queue8.judgeCount); // 1.5w
}
}
如果 n = 1，A -> C
如果 n >= 2，總是看做是兩個盤，①最下邊的盤。②上面所有的盤。則，步驟：
（1）先把上面所有的盤 A->B
（2）把最下邊的盤 A->C
（3）把 B 塔的所有盤 從 B->C
代碼示例：漢諾塔問題
// 漢諾塔
public class Hanoitower {
// 使用分治算法
public static void move(int num, char a, char b, char c) {
// 如果只有一個盤
if (num == 1) {
System.out.println("第1個盤從 " + a + "->" + c);
} else {
// n >= 2，總是看做是兩個盤，①最下邊的盤。②上面所有的盤。則，步驟：
// 1.先把上面所有的盤 A->B.移動過程會使用到 c
move(num - 1, a, c, b);
// 2.把最下邊的盤 A->C
System.out.println("第" + num + "個盤從 " + a + "->" + c);
// 3.把 B 塔的所有盤 從 B->C.移動過程會使用到 a
move(num - 1, b, a, c);
}
}
}代碼示例：測試類
// 測試類
public class Main {
public static void main(String[] args) {
Hanoitower.move(3, 'A', 'B', 'C');
}
}// 結果
第1個盤從 A->C
第2個盤從 A->B
第1個盤從 C->B
第3個盤從 A->C
第1個盤從 B->A
第2個盤從 B->C
第1個盤從 A->C
以上是“Java如何實現遞歸算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
