1 何謂遞歸？
重復是許多算法的一個特性，兩種問題的處理方法可以求解，被稱為迭代和遞歸。
迭代：是大家所熟悉的循環(huán)語句，不管是for， while， 還是do。循環(huán)中都會有需要重復執(zhí)行的語句，以及控制重復次數(shù)的機制。迭代提供了解決一種重復性過程的直接而有效的方法。
遞歸：有些遞歸求解的方法可能是最佳方案，有些因為低效而全然不應該使用。
在解決一個問題時，更小的問題除了問題規(guī)模以外，其他的方面都是一樣的。這種特殊情況的處理方式就是遞歸。那么問題需要解決的就是一個規(guī)模更小而其他方面與原問題一樣的問題。如何用另一個問題替代原問題，并得到最終解呢？
遞歸成功的關鍵之一就是，最終稿到達一個其解已知的小規(guī)模問題，該小規(guī)模問題的解或者是顯然易見，或者是已知的。求得小規(guī)模的解后，通常是原來問題的一部分，這部分再與其他部分解結合在一起，組成規(guī)模更大的問題的解
總結
遞歸是一種問題的求解方式，即將一個問題分解成為諾干相似但是規(guī)模更小的問題。
調用自身的方法為遞歸方法，這個調用就成為遞歸調用
1.2跟蹤遞歸方法
java會記錄該方法的執(zhí)行狀態(tài)，包括其形參和局部變量的值以及當前指令的位置，每一個記錄被稱為活動記錄，提供了對方法執(zhí)行期間的一個活動快照。這些記錄被存在一個棧的ADT里面。當前執(zhí)行的方法位于棧頂。
所以遞歸方法可能造成棧溢出的錯誤。
遞歸方法本身沒有什么缺陷的，但是在現(xiàn)代的計算機系統(tǒng)中，執(zhí)行遞歸的方法的方式是棧，所以對于很大的n時，很可能造成棧溢出。
2 設計遞歸方法
2.1首先得思考是否能夠遞歸實現(xiàn)：
- 什么樣的規(guī)模更小但是實質是相同的問題，其解與直接得出的部分解一起可以構成原問題的解
- 解的哪一部分可以直接得出
- 整個過程什么時候結束？-->相同實質的問題什么時候有已知解-->是否達到這個小規(guī)模或者是基本情況
2.2具體的設計方法：
- 方法必須傳入一個值，這個值是用來控制遞歸的過程
- 方法的定義需要包括一個邏輯，方法必須以這個輸入值作為導致不同情況的參數(shù)，邏輯一般是if或者是while的
- 其中一個或者多個情況是不需要遞歸的解，這樣的情況是基本情況或者是終止情況
- 其中一個或者是多個必須包含對方法的遞歸調用，這些遞歸在某種意義上通過“更小的值”或者是“更小的任務”推進
3 常見的遞歸demo
熟記這幾個demo，是后序高級排序算法會經常用到的
3.1 遞歸處理數(shù)組
3.1.1遍歷數(shù)組
思路分析：
首先思考是否具備遞歸的條件：根據(jù)2.1的思考步驟，
是否有更小的又實質相同的問題？要遍歷整個list，那么分成小問題，就是每次要遍歷第一個數(shù)字。這就是遞歸的方法
哪一部分可以直接得到？第一個數(shù)
代碼的設計：
遞歸的結構：遍歷數(shù)組的就是每次讀取一個list的第一個
終止的條件：達到數(shù)組的尾端，就是star<end（這個條件是因為在數(shù)組中是以0開始的，所以最后一個元素的位置是end-1）
控制方法推進的條件：讀取完一個數(shù)字就把star+1
方法的設計：傳入?yún)?shù)為，一個數(shù)組還有遍歷數(shù)組的起點和終點
/**
* 遞歸遍歷一個數(shù)組
* star : 開始遍歷的數(shù)字，從1開始
*/
public static void displayArrayByRecursion(int[] list, int start, int end) {
// 這是更小的但是實質又是相同的步驟
System.out.print(list[start - 1] + " ");
// 這里是控制遞歸的結束語句
if (start < end) {
// 這里的star+1 是推進代碼方法的進程
displayArrayByRecursion(list, start + 1, end);
}
}
