何為遞歸从绘？
所謂遞歸寄疏，簡單點來說，就是一個函數(shù)直接或間接調(diào)用自身的一種方法僵井，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。
我們可以把” 遞歸 “比喻成 “查字典 “驳棱，當(dāng)你查一個詞批什，發(fā)現(xiàn)這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞社搅∽ふ可惜，第二個詞里仍然有不懂的詞形葬，于是查第三個詞合呐，這樣查下去，直到有一個詞的解釋是你完全能看懂的笙以，那么遞歸走到了盡頭淌实，然后你開始后退，逐個明白之前查過的每一個詞猖腕，最終拆祈，你明白了最開始那個詞的意思。（摘自知乎的一個回答）
遞歸函數(shù)
所謂遞歸函數(shù)是自身調(diào)用自身倘感，在執(zhí)行遞歸函數(shù)時放坏，系統(tǒng)會把遞歸函數(shù)的全部信息壓入棧中，且每次進(jìn)行子操作時老玛，棧會記錄當(dāng)前操作的變量淤年，待子操作完成時恢復(fù)最初的現(xiàn)場±總之麸粮，一切非遞歸函數(shù)皆可轉(zhuǎn)換為遞歸函數(shù)。
遞歸函數(shù)的復(fù)雜度
T(n) = aT(n/b) + O(n ^d)
- log(b,a) > d ===> 復(fù)雜度為O(n^ log(b,a))
- 2.log(b,a) = d ===> 復(fù)雜度為O(n^d * logN)
- 3.log(b,a) < d ===> 復(fù)雜度為O(n^d)
其中余素，T(n) 表示數(shù)據(jù)樣本量為n時的時間復(fù)雜度豹休，aT(n/b)表示自操作的時間復(fù)雜度，其中a表示子操作次數(shù)桨吊，n/b表示子操作的數(shù)據(jù)樣本量威根，O(n^d)表示除去子操作外常規(guī)的比較時間的時間復(fù)雜度。注意视乐，使用上述函數(shù)的前提是子操作的樣本量應(yīng)該相等洛搀。
舉列說明：求數(shù)組的最大值
public class Recursion {
public static int getMax(int []arr, int L, int R ) {
if(L == R) {
return arr[L];
}
int mid = (L+R)/2;
int maxLeft = getMax(arr, L, mid);
int maxRight = getMax(arr, mid+1, R);
return Math.max(maxLeft, maxRight);
}
}
上述遞歸函數(shù)中，將一個數(shù)組劃為左右兩部分進(jìn)行查找最大值佑淀，然后進(jìn)行比較留美，得出數(shù)組的最大值，可以看出，每次子操作的樣本量為n/2,總共左右兩次操作谎砾，d=0,常規(guī)的比較時間為O(1),故本次遞歸函數(shù)的時間復(fù)雜度為T(n) = 2(n/2) + O(1);
