遞歸算法基礎(chǔ)
在計算機(jī)編程應(yīng)用中，遞歸算法對解決大多數(shù)問題都是十分有效的，主要是因?yàn)樗軌蚴顾惴ǖ拿枋鲎兊煤啙嵑鸵子诶斫?，主要?個特點(diǎn)。
- 遞歸過程一般通過函數(shù)或子過程來實(shí)現(xiàn)
- 遞歸算法在函數(shù)或子過程的內(nèi)部，直接或間接地調(diào)用自己的算法。
- 遞歸算法實(shí)際上是把問題轉(zhuǎn)化成規(guī)?？s小了的同類問題的子問題，然后再遞歸調(diào)用函數(shù)或過程來表示問題的解。
使用遞歸算法時，應(yīng)該注意以下4點(diǎn)：
- 遞歸是在過程或者函數(shù)中調(diào)用自身的過程
- 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱之為遞歸出口
- 遞歸算法通常顯得很簡潔，但是運(yùn)行效率較低，所以一般不提倡使用
- 在遞歸調(diào)用過程中，系統(tǒng)通過棧來存儲每一層的返回點(diǎn)和局部量。如果遞歸次數(shù)過多，很容易造成棧溢出(StackOverflowError)
例如：
public class stack {
private static int index = 1;
public static void main(String[] args) {
try {
test();
} catch (StackOverflowError e) {
System.out.println(index);
e.printStackTrace();
}
}
public static void test() {
index++;
test();
}
}
通過遞歸不斷地去調(diào)用自身，超過系統(tǒng)的棧的深度就會直接報錯
接下來通過漢諾塔的例子具體講解一下遞歸過程
首先什么是漢諾塔呢？
在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。
okay，我們的目標(biāo)是要把第一個柱子上的64片移到第三個柱子上面去
- 首先第一輪可以把前63片移到第二個柱子上面去，再把第64片移到第三個柱子上面去，再把第二個柱子上面的63片移到第三個柱子上面
- 那么，第二輪的問題是怎么把前63片移到第二個柱子，可以先把前62片移到第三個柱子上面去，再把第63片移到第二個柱子上面去，再把第三個柱子上面的62片移到第二個柱子上面
- .......
- 到了最上面一片只需要將第一片移開，把第二片移到另一個空柱子，再把第一片移到第二片上面去，完成整個操作(第一片移到哪個柱子取決于你的片數(shù)的奇偶)
這樣就形成了遞歸，在你調(diào)用move(n,a,b,c)的時候，只需要讓n-1個片移到b上面去(move(n-1,a,c,b))，再把第n個片移到c，緊接著把b上面的n-1個片移到c上面去(move(n-1,b,a,c))，就可以完成整個操作。
從結(jié)果上面來看，需要搬移的次數(shù)為2^n - 1
public class HanoiTest {
private static int count;
public static void main(String[] args) {
move(64,'a','b','c');
System.out.println(count);
}
private static void move(int n,int a,int b,int c) {
if (n == 1) {
count++;
System.out.println((char)a +"-->"+ (char)c);
} else {
move(n-1,a,c,b);
count++;
System.out.println((char)a +"-->"+ (char)c);
move(n-1,b,a,c);
}
}
}
