遞歸
簡介
遞歸 問題是數(shù)學(xué)中一種解決問題的思想，和遞推剛好是相對的。我們說 遞推 就是講一個問題從正面入手一點一點的抽絲剝繭，而 遞歸 則是從敵后直搗黃龍拢操。
例子
這里我創(chuàng)建了一個 Recursion 類，類中定義了 getRecursion 方法舶替，使用 getRecursion 進行遞歸調(diào)用令境，實現(xiàn)從10遞減到0的操作。
public class Recursion{
public static void getRecursion(int i) {
System.out.println(i);
if (i > 0){
i--;
getRecursion(i);
}
}
public static void main(String[] args) {
int i = 10;
getRecursion(i);
}
}
漢諾塔問題
這里我不再講解漢諾塔問題的描述顾瞪，如果不清楚的可以自行去百度了解舔庶。
漢諾塔問題我們可以從三階漢諾塔分析
漢諾塔
常見的三階漢諾塔運用遞歸思想我們可以理解為三個子問題：
-
從 A 我們將上面兩層轉(zhuǎn)移到 B
從A到B問題 -
從 A 我們將最下面一個元素轉(zhuǎn)移到 C
從A將最下面的轉(zhuǎn)移到C -
從 B 我們將之間從 A 轉(zhuǎn)移到 B 的兩層轉(zhuǎn)移到 C
從B轉(zhuǎn)移到C
Java代碼實現(xiàn)
public class Recursion{
/*
* n 表示漢諾塔的階數(shù)
* a，b陈醒，c 代表三個桿子惕橙，其中 a 表示要轉(zhuǎn)移的的桿子，b 代表中間轉(zhuǎn)換的桿子钉跷，c 代表目標(biāo)桿子
* 總共分為三步
**/
public static void hanoi(int n,String a,String b,String c){
if (n > 0){
//第一步弥鹦，將 A 中除最后一個都轉(zhuǎn)移到 B
hanoi(n-1,a,c,b);
//將 A 的最下面一個轉(zhuǎn)移到 C
System.out.println(" move " a + " to " + c);
//將 B 的所有元素轉(zhuǎn)移到 C
hanoi(n-1,b,a,c);
}
}
public static void main(String[] args) {
hanoi(3,"A","B","C");
}
}
當(dāng)然以后的更多層的漢諾塔我們同樣也可以用同樣的方法去解決。
