一，充分利用自己的遞歸算法思想
遞歸算法能夠充分挖掘自身的潛力，無論遇到了什么問題，它都會直接或者間接地調(diào)用自身的算法去解決。
遞歸算法思想的原則是有事不求人。即使難以解決解決也要自己解決，即使難以解決也要硬著頭皮去解決。遞歸的自身算法往往用函數(shù)的形式體現(xiàn)，所以遞歸算法需要預(yù)先編寫功能函數(shù)，這些函數(shù)是獨立的功能，能夠?qū)崿F(xiàn)解決某個問題的具體功能，當(dāng)需要時直接調(diào)用這個函數(shù)即可。
1，遞歸算法的基礎(chǔ)
在計算機編程應(yīng)用中，遞歸算法對解決大多數(shù)問題是十分有效的，她能夠使算法的描述變得簡介而且易于理解，遞歸算法有如下3個特點：
（1）遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。
（2）遞歸算法在函數(shù)或子過程的內(nèi)部，直接或者簡介地調(diào)用自己的算法。
（3）遞歸算法實際上是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題，然后在遞歸調(diào)用函數(shù)或過程來表示問題的解。
2 ，在使用遞歸算法時，注意一下幾點 （1）遞歸是在過程或 函數(shù)中調(diào)用自身的過程
（2）在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，這稱為遞歸出口。
（3）遞歸算法通常顯得很簡潔，但是運算效率較低，所以一般不提倡使用遞歸算法設(shè)計程序。
（4）在遞歸調(diào)用過程中，系統(tǒng)用棧來存儲每一層的的返回點和局部變量。如果遞歸次數(shù)過多，則容易造成棧溢出，所以一般不提倡用遞歸算法設(shè)計程序。
3，實例----------漢諾塔問題：
一個廟里有三個柱子，第一個有64個盤子，從上往下盤子越來越大。要求廟里的老和尚把這64個盤子全部移動到第三個柱子上。移動的時候始終只能小盤子壓著大盤子。而且每次只能移動一個。
1、此時老和尚（稱為第1個和尚）他想：要是有一個人能把前63個盤子先移動到第二個柱子上，我再把最后一個盤子直接移動到第三個柱子，再讓那個人把剛才的前63個盤子從第二個柱子上移動到第三個柱子上，我的任務(wù)就完成了，簡單。所以他找了第2個和尚，讓其：
① 你把前63個盤子移動到第二柱子上
② 在我自己把第64個盤子一道第三個柱子上后
③ 你把前63個盤子移動到第三柱子上
2、第2個和尚接了任務(wù)后和第1個和尚一樣想：要是有一個人能把前62個盤子先移動到第三個柱子上，我再把最后一個盤子直接移動到第二個柱子，再讓那個人把剛才的前62個盤子從第三個柱子上移動到第三個柱子上，我的任務(wù)就完成了，所以他也找了比他年輕的和尚叫他第3和尚，讓其：
① 你把前62個盤子移動到第三柱子上
② 在我自己把第63個盤子一道第二個柱子上后
③ 你把前62個盤子移動到第二柱子上
3、第3個和尚接了任務(wù)，又把移動前61個盤子的任務(wù)依葫蘆話瓢的交給了第4個和尚，等等遞推下去，直到把任務(wù)交給了第64個和尚為止（估計第64個和尚很郁悶，沒機會也命令下別人，因為到他這里盤子已經(jīng)只有一個了）。
4、到此任務(wù)下交完成，到各司其職完成的時候了。完成回推了：
第64個和尚移動第1個盤子，把它移開，然后第63個和尚移動他給自己分配的第2個盤子。第64個和尚再把第1個盤子移動到第2個盤子上。到這里第64個和尚的任務(wù)完成，第63個和尚完成了第62個和尚交給他的任務(wù)的第一步。
從上面可以看出，只有第64個和尚的任務(wù)完成了，第63個和尚的任務(wù)才能完成，只有第2個和尚任務(wù)完成后，第1個和尚的任務(wù)才能完成。這是一個典型的遞歸問題。
遞歸（recursion）：程序調(diào)用自身的編程技巧。
遞歸滿足2個條件：
1）有反復(fù)執(zhí)行的過程（調(diào)用自身）
2）有跳出反復(fù)執(zhí)行過程的條件（遞歸出口）
遞歸與棧的關(guān)系
下面演示的是求n的階乘
intFactorial(int n){
if(n == 0)return1; returnn * Factorial(n - 1);
}
常常聽到 “遞歸的過程就是出入棧的過程”，這句話怎么理解？我們以上述代碼為例，取 n=3，則過程如下：
第 1~4 步，都是入棧過程，F(xiàn)actorial(3)調(diào)用了Factorial(2)，F(xiàn)actorial(2)又接著調(diào)用Factorial(1)，直到Factorial(0)；
第 5 步，因 0 是遞歸結(jié)束條件，故不再入棧，此時棧高度為 4，即為我們平時所說的遞歸深度；
第 6~9 步，F(xiàn)actorial(0)做完，出棧，而Factorial(0)做完意味著Factorial(1)也做完，同樣進(jìn)行出棧，重復(fù)下去，直到所有的都出棧完畢，遞歸結(jié)束。
每一個遞歸程序都可以把它改寫為非遞歸版本。我們只需利用棧，通過入棧和出棧兩個操作就可以模擬遞歸的過程，二叉樹的遍歷無疑是這方面的代表。
但是并不是每個遞歸程序都是那么容易被改寫為非遞歸的。某些遞歸程序比較復(fù)雜，其入棧和出棧非常繁瑣，給編碼帶來了很大難度，而且易讀性極差，所以條件允許的情況下，推薦使用遞歸。
示例題目
1.有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第四個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數(shù)為多少對？請使用遞歸和非遞歸實現(xiàn)。
import java.util.Scanner;publicclass Main{/** 兔子的規(guī)律為數(shù)列1,1,2,3,5,8,13,21.... 這是一個菲波拉契數(shù)列問題 {斐波拉契數(shù)列原理：除開前兩項 后面每位數(shù)等于前兩項相加之和}
* 1.通過中間值來保存上一月兔子的和 2.在將上一月兔子這一月兔子相加 得到下一月數(shù)量和*/// 非遞歸publicstaticvoidf1(int month) {intrabbit = 1;// 上月兔子的數(shù)量和intnewRabbit = 1;// 這一月生成兔子的數(shù)量和intcount;// 中間值 用來存數(shù)量的if(month == 1) {
System.out.println("第1月兔子 1 對");
} elseif(month == 2) {
System.out.println("第2月兔子 1 對");
} else {// 從第三月起for(inti = 3; i <= month; i++) {
count = newRabbit;
newRabbit = rabbit + newRabbit;
rabbit = count;
}
System.out.println("第" + month + "月兔子 " + newRabbit + " 對");
}
}// 遞歸publicstaticintf2(int month) {if(month == 1 || month == 2) {return1;
}// 上一個月的兔子數(shù)intrabbit1 = f2(month - 1);// 上一個月的前一個月兔子數(shù)intrabbit2 = f2(month - 2);returnrabbit1 + rabbit2;
}publicstaticvoid main(String[] args) {
Scanner sc =new Scanner(System.in);intmonth = sc.nextInt();
f1(month);
System.out.println("============");
System.out.println("第" + month + "月兔子 " + f2(month) + " 對");
}
}
2.十進(jìn)制轉(zhuǎn)二進(jìn)制
import java.util.Scanner;/*
* 十進(jìn)制轉(zhuǎn)二進(jìn)制*/publicclass Main {// 非遞歸publicstaticvoidf1(int n) {intt = 0;intbin = 0;intr = 0;while(n != 0) {
r = n % 2;
n = n / 2;
bin += r * Math.pow(10, t);
t++;
}
System.out.println(bin);
}// 遞歸publicstaticvoidf2(int n) {if(n / 2 == 0) {
System.out.print(n % 2);
} else {
f2(n / 2);
System.out.print(n % 2);
}
}publicstaticvoid main(String[] args) {
System.out.println("請輸入一個非負(fù)的十進(jìn)制整數(shù):");
Scanner sc =new Scanner(System.in);intnumber = sc.nextInt();if(number < 0) {
System.out.println("不符合要求");
} else {
System.out.print("對應(yīng)的二進(jìn)制:");
f1(number);
System.out.println("=================");
System.out.print("對應(yīng)的二進(jìn)制:");
f2(number);
}
}
}
