锲而舍之，朽木不折；锲而不舍，金石可镂。
---荀子《勸學》
1. 從思想上了解遞歸
遞歸行為從大問題劃分為同等結構的小問題着手，每個小問題都和上一級的大問題是同等結構，同等結構的小問題解決了之後所收集來的資訊通過分析能夠整合出大問題的傳回值。
遞歸就是 「以大化小」 的解決思路。
2. 程式如何運作遞歸函數
從一個例子來了解遞歸。
求數組arr[L..R]中的最大值，怎麼用遞歸方法實作。
1）将[L..R]範圍分成左右兩半。左：[L..Mid] 右：[Mid+1..R] 2）左部分求最大值，右部分求最大值 3） [L..R]範圍上的最大值，是max{左部分最大值，右部分最大值}
注意：
左部分求最大值，右部分求最大值
是個遞歸過程，當範圍上隻有一個數，就可以不用再遞歸了。
首先，我們把這個遞歸函數先寫出來，然後分析遞歸函數在系統中是如何運作的。
public int process(int[] arr, int L, int R) {
//base case
if (L == R) {
return arr[L];
}
int mid = (L + R) >> 1;
//遞歸
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(lmax, rMax);
}
複制
給定數組arr = {3, 7, 6, 8, 2, 4, 7, 9}，
數組及其索引下标
要找到該數組的最大元素，就是要調用函數 「process(arr, 0, 7)」 ，執行步驟：
L = 0, R = 7，此時mid = (0 + 7) / 2 = 3，程式運作到第8行 「int leftMax = process(arr, L, mid);」 處時，程式好像又傳回去執行了函數 「process(arr, 0, 3)」 ，那麼它在系統中其實是暫時把之前運作的一些列 「中間資訊暫存到系統棧」 中，此時棧結構：
L = 0，R = 3，此時mid = (0 + 3) / 2 = 1，程式由運作到 「int lMax = process(arr, L, mid);」 位置，即執行函數 「process(arr, 0, 1)」 ，此時又将這一步的中間結果壓入系統棧：
L = 0，R = 1，此時mid = (0 + 1) / 2 = 0，程式執行 「int lMax = process(arr, L, mid);」 即執行函數 「process(arr, 0, 0)」 ，此時 L==R，傳回arr[L]，也就是arr[0]=3，此時系統棧情況：
這個時候，彈出系統棧頂，并記住此時的leftMax = 3。
此時的棧：
據此恢複遞歸函數的執行現場：
process(arr,0,1)
mid=0
leftMax=3
rightMax=process(arr,1,1)
複制
虛線棧幀彈出，此時計算出了 「process(arr, 0, 1)」 即arr數組0 ~ 1上的最大值，第10行計算出了0~1上的最大值為7。
此時還原到上一次的遞歸函數執行現場：
process(arr,0,3)
mid=1
leftMax=process(arr,0,1)=7
rightMax=process(arr,2,3)
複制
繼續上述類似入棧步驟，每次入棧都記錄程式執行的行數、中間變量等資訊。
「TIP：」 遞歸函數執行過程中，系統幫我們把運作過程中的一些中間資訊放到棧中，如果我們自己做一個棧，改成疊代行為，也是可以實作的。是以，「遞歸函數都可以改寫成非遞歸函數。」
3. 遞歸函數調用圖解
針對上述遞歸函數，後續我們可以這麼畫圖模拟調用：
遞歸過程圖
這就是遞歸調用的邏輯圖。把調用的過程畫出結構圖是必須的，這有利于分析遞歸。
通過一個簡單例題的分析得知，遞歸底層是利用系統棧來實作的。平時分析遞歸的時候，建議畫出邏輯圖來輔助分析遞歸行為。
4. 計算遞歸算法時間複雜度-Master公式
計算遞歸算法的時間複雜度可以用Master公式：
時間複雜度為形如
T(N) = aT(\frac{N}{b}) + O(N^d)，其中a、b、d為常數
的遞歸函數，可以直接通過以下條件來确定時間複雜度：
如果 \log_ba < d，時間複雜度為 O(N^d)
如果 \log_ba >d， 時間複雜度為 O(N\log_ba)
如果 \log_ba == d， 時間複雜度為 O(N^d\log_ba)
針對本文一開始提出的求數組最大值問題，來根據Master公式分析一下其時間複雜度。
對于數組arr，假設有N個資料的規模，擷取最大值的時間複雜度記為：
T(N)
根據代碼，我們把它分為了左側部分和右側部分，其資料量分别為N / 2（即「子遞歸資料規模同等」），是以，左右兩側遞歸計算的時間複雜度分别為：
T(\frac{N}{2})
是以有：
T(N) = 2 T(\frac{N}{2}) + 計算max(leftMax，rightMax)的時間
該遞歸函數整體上還有一部分時間是計算 「leftMax」 和 「rightMax」 的最大值的，這部分的時間複雜度為O(1)，是以，該遞歸函數的時間複雜度就是：
T(N) = 2T(\frac{N}{2}) + O(1)
是以代入到時間複雜度公式，有：
\log_ba = \log_22 = 1
O(N^d) = O(1) =>d = 0
是以，得出以下條件
\log_ba >d
再是以，該遞歸函數的時間複雜度為：
O(N\log_ba) = O(N\log_22) = O(N)
「TIP：」 使用Master公式計算遞歸時間複雜度的前提：劃分的子遞歸的規模是一樣的，即 「同等規模的子遞歸」 。
首發公衆号 「行百裡er」 ，歡迎老鐵們關注閱讀指正。代碼倉庫 「GitHub」 https://github.com/xblzer/JavaJourney