~~~
總體來說遞歸基本可表述成以下類似的結構：
遞歸調用(參數) {
if (基本情形) {
// ...
// 完成，收工
} else { // 遞歸情形
// ...
遞歸調用( 新參數 );
}
}
因此，寫遞歸程序一是明確基本情形，二是找出遞歸情形。
~~~
### eg1:求階乘
也就是輸入一個數,然后求出他的階乘,例如輸入5,則求5!=120
**分析:**
畫出示意圖如下:
可以看出基本情形就是1!=1,特殊情形就等于f(n-1),所以程序如下
~~~
private static int getIndex(int n) {
if (n==1) {
return 1;//基本情況
}else{
return n * getIndex(n-1);//特殊情況
}
}
~~~
### eg2:斐波那契數列
輸入一個數表示斐波那契數列的第幾項,然后找出這一項的值
**分析:**
可以看出基本情景就是f(2)=1,f(1)=1,特殊情景就是f(n-1)+f(n-2)
所以程序如下
~~~
private static int getIndex(int n) {
if (n==1||n==2) {
return 1;//基本情況
}else{
return getIndex(n-1)+getIndex(n-2);//特殊情況
}
}
~~~
### eg3:漢諾塔問題
大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
**分析**三個柱子分別是ABC,現在要從A移動到C
當只有一個盤子時,只需要A->C
當有兩個盤子的時候,先A->B,再A->C,再B->C
當有三個盤子的時候,先把前兩個借助C移動到B,然后再把第三個移動到C,剩下兩個再如此進行
當有N個盤子的時候,先把N-1個盤子借助C移動到B,再把第N個移動到C,剩下N-1個盤子,再借助C移動到AN-2個,再把第N-1個盤子移動到C,如此循環
對于圖片又要解釋的就是,移動分兩步,一步是移動到目標,另一步則是借助一個柱子,移動N-1個到空閑柱子,那基本情況就是當盤子為1的時候,直接移動到目標,代碼如下
~~~
private static void move(int n,char from,char to,int i){
System.out.println("移動第"+n+"個盤子從"+from+"-->"+to+"--"+i);
}
private static void hanoi(int n,char from,char depand_on,char to){
if (n==1) {
move(n, from, to,1);//如果只剩最后一個盤子就將盤子移動到指定位置
}else {
hanoi(n-1, from, to, depand_on);
move(n, from, to,0);
hanoi(n-1, depand_on, from, to);
}
}
~~~
看輸入,每動其他盤子,后面必要動第一個盤子,也就是執行N==1這個情況
