1、遞歸算法定義
遞歸算法是將重復問題分解為同類的子問題而解決問題的方法，其核心思想是分治策略。
簡單來說就是自己調用自己。直到達到退出遞歸的條件，則完成遞歸。
2、遞歸的步驟
1、找整個遞歸的終止條件：遞歸應該在什么時候結束？
2、找返回值：應該給上一級返回什么信息？
3、本級遞歸應該做什么：在這一級遞歸中，應該完成什么任務？
3、遞歸的優點和缺點
優點：遞歸的核心思想就是將一個大問題，拆解成一個小問題，然后將小問題再次拆解，層層拆分從而簡化問題的實現。從而達到簡化重復的代碼讓程序變得更加簡潔。
缺點：使用遞歸算法時每次方法的調用都需要在棧中開辟出一個空間保存相關數據，頻繁的壓棧、彈棧會導致效率變低。
4、遞歸的案例
4.1 階乘的算法
? ? // 階乘的遞歸實現
? ? public static long f(int n){
? ? ? ? if(n == 1)? ?// 結束遞歸終止條件?
? ? ? ? ? ? return 1;? ?
?
? ? ? ? return n*f(n-1);? // 相同重復邏輯，縮小問題的規模
? ? }
4.2?斐波納契數列
斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……
在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
public static int fibonacci(int n) {
? ? ? ? if (n == 1 || n == 2) {? ? ?// 遞歸終止條件
? ? ? ? ? ? return 1;? ? ? ?// 簡單情景
? ? ? ? }
? ? ? ? return fibonacci(n - 1) + fibonacci(n - 2); // 相同重復邏輯，縮小問題的規模
}
4.3 ?漢諾塔問題
/**?
* Title: 漢諾塔問題?
* Description:古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。?
* 有一個和尚想把這64個盤子從A座移到C座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，?
* 小盤在上。在移動過程中可以利用B座。要求輸入層數，運算后輸出每步是如何移動的。?
*?
?*/
public class HanoiTower {
?
? ? /**? ? ?
? ? ?* @description 在程序中，我們把最上面的盤子稱為第一個盤子，把最下面的盤子稱為第N個盤子
? ? ?* @author rico? ? ? ?
? ? ?* @param level：盤子的個數
? ? ?* @param from 盤子的初始地址
? ? ?* @param inter 轉移盤子時用于中轉
? ? ?* @param to 盤子的目的地址
? ? ?*/
? ? public static void moveDish(int level, char from, char inter, char to) {
?
? ? ? ? if (level == 1) { // 遞歸終止條件
? ? ? ? ? ? System.out.println("從" + from + " 移動盤子" + level + " 號到" + to);
? ? ? ? } else {
? ? ? ? ? ? // 遞歸調用：將level-1個盤子從from移到inter(不是一次性移動，每次只能移動一個盤子,其中to用于周轉)
? ? ? ? ? ? moveDish(level - 1, from, to, inter); // 遞歸調用，縮小問題的規模
? ? ? ? ? ? // 將第level個盤子從A座移到C座
? ? ? ? ? ? System.out.println("從" + from + " 移動盤子" + level + " 號到" + to);?
? ? ? ? ? ? // 遞歸調用：將level-1個盤子從inter移到to,from 用于周轉
? ? ? ? ? ? moveDish(level - 1, inter, from, to); // 遞歸調用，縮小問題的規模
? ? ? ? }
? ? }
?
? ? public static void main(String[] args) {
? ? ? ? int nDisks = 30;
? ? ? ? moveDish(nDisks, 'A', 'B', 'C');
? ? }
4.4 二叉樹深度?
public static int getTreeDepth(Tree t) {?
? ? ? ? // 樹為空
? ? ? ? if (t == null) // 遞歸終止條件
? ? ? ? ? ? return 0;?
? ? ? ? int left = getTreeDepth(t.left); // 遞歸求左子樹深度，縮小問題的規模
? ? ? ? int right = getTreeDepth(t.left); // 遞歸求右子樹深度，縮小問題的規模?
? ? ? ? return left > right ? left + 1 : right + 1;
? ? }
?
?
?
IT技術分享社區
個人博客網站：https://programmerblog.xyz
文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識
?1、遞歸算法定義
遞歸算法是將重復問題分解為同類的子問題而解決問題的方法，其核心思想是分治策略。
簡單來說就是自己調用自己。直到達到退出遞歸的條件，則完成遞歸。
2、遞歸的步驟
1、找整個遞歸的終止條件：遞歸應該在什么時候結束？
2、找返回值：應該給上一級返回什么信息？
3、本級遞歸應該做什么：在這一級遞歸中，應該完成什么任務？
3、遞歸的優點和缺點
優點：遞歸的核心思想就是將一個大問題，拆解成一個小問題，然后將小問題再次拆解，層層拆分從而簡化問題的實現。從而達到簡化重復的代碼讓程序變得更加簡潔。
缺點：使用遞歸算法時每次方法的調用都需要在棧中開辟出一個空間保存相關數據，頻繁的壓棧、彈棧會導致效率變低。
4、遞歸的案例
4.1 階乘的算法
? ? // 階乘的遞歸實現
? ? public static long f(int n){
? ? ? ? if(n == 1)? ?// 結束遞歸終止條件?
? ? ? ? ? ? return 1;? ?
?
? ? ? ? return n*f(n-1);? // 相同重復邏輯，縮小問題的規模
? ? }
4.2?斐波納契數列
斐波納契數列，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……
在數學上，斐波納契數列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。
public static int fibonacci(int n) {
? ? ? ? if (n == 1 || n == 2) {? ? ?// 遞歸終止條件
? ? ? ? ? ? return 1;? ? ? ?// 簡單情景
? ? ? ? }
? ? ? ? return fibonacci(n - 1) + fibonacci(n - 2); // 相同重復邏輯，縮小問題的規模
}
4.3 ?漢諾塔問題
/**?
* Title: 漢諾塔問題?
* Description:古代有一個梵塔，塔內有三個座A、B、C，A座上有64個盤子，盤子大小不等，大的在下，小的在上。?
* 有一個和尚想把這64個盤子從A座移到C座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，?
* 小盤在上。在移動過程中可以利用B座。要求輸入層數，運算后輸出每步是如何移動的。?
*?
?*/
public class HanoiTower {
?
? ? /**? ? ?
? ? ?* @description 在程序中，我們把最上面的盤子稱為第一個盤子，把最下面的盤子稱為第N個盤子
? ? ?* @author rico? ? ? ?
? ? ?* @param level：盤子的個數
? ? ?* @param from 盤子的初始地址
? ? ?* @param inter 轉移盤子時用于中轉
? ? ?* @param to 盤子的目的地址
? ? ?*/
? ? public static void moveDish(int level, char from, char inter, char to) {
?
? ? ? ? if (level == 1) { // 遞歸終止條件
? ? ? ? ? ? System.out.println("從" + from + " 移動盤子" + level + " 號到" + to);
? ? ? ? } else {
? ? ? ? ? ? // 遞歸調用：將level-1個盤子從from移到inter(不是一次性移動，每次只能移動一個盤子,其中to用于周轉)
? ? ? ? ? ? moveDish(level - 1, from, to, inter); // 遞歸調用，縮小問題的規模
? ? ? ? ? ? // 將第level個盤子從A座移到C座
? ? ? ? ? ? System.out.println("從" + from + " 移動盤子" + level + " 號到" + to);?
? ? ? ? ? ? // 遞歸調用：將level-1個盤子從inter移到to,from 用于周轉
? ? ? ? ? ? moveDish(level - 1, inter, from, to); // 遞歸調用，縮小問題的規模
? ? ? ? }
? ? }
?
? ? public static void main(String[] args) {
? ? ? ? int nDisks = 30;
? ? ? ? moveDish(nDisks, 'A', 'B', 'C');
? ? }
4.4 二叉樹深度?
public static int getTreeDepth(Tree t) {?
? ? ? ? // 樹為空
? ? ? ? if (t == null) // 遞歸終止條件
? ? ? ? ? ? return 0;?
? ? ? ? int left = getTreeDepth(t.left); // 遞歸求左子樹深度，縮小問題的規模
? ? ? ? int right = getTreeDepth(t.left); // 遞歸求右子樹深度，縮小問題的規模?
? ? ? ? return left > right ? left + 1 : right + 1;
? ? }
?
?
?
IT技術分享社區
個人博客網站：https://programmerblog.xyz
文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識
?
...)
)
