原來在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的時候，學(xué)習(xí)到遞歸侧戴，當(dāng)時覺得遞歸就是一種自己調(diào)用自己的方法嘛，只要控制好遞歸的結(jié)束條件就可以了跌宛⌒锼危可是在工作之后才發(fā)現(xiàn)，對于很多問題疆拘，采用遞歸的思想可以大大降低實現(xiàn)的難度（暫時先不考慮效率）蜕猫，所以決定好好的研究一下遞歸。
什么是遞歸
遞歸方法對應(yīng)于數(shù)學(xué)上的歸納法哎迄，把一個想要解決的問題轉(zhuǎn)化為解決他的子問題回右，子問題又可以繼續(xù)轉(zhuǎn)化為子問題的子問題，這些子問題與原問題有著相同的結(jié)構(gòu)或者說有著相同的模型漱挚。當(dāng)然了這些子問題并不是可以無限分解的翔烁，使的問題不能繼續(xù)分解下去的條件被我們稱為遞歸結(jié)束條件。
遞歸從大的方面旨涝，分為兩個步驟：遞和歸蹬屹。把問題分解為子問題的過程屬于"遞"，到達(dá)了遞歸結(jié)束條件，使得子問題出棧的過程屬于"歸"
一般的遞歸都分為：
- 結(jié)束條件
- 直接求解表達(dá)式慨默。就是在到達(dá)結(jié)束條件的時候贩耐，我們可以直接用來求解的表達(dá)式
- 步進(jìn)表達(dá)式和歸納項。之所以把這兩個合為一個厦取，是因為這兩個經(jīng)常會一起用潮太。步進(jìn)表達(dá)式是可以使得遞歸可以繼續(xù)向下分解的表達(dá)式。歸納項是只在這一次遞歸過程中蒜胖，我們對于該子問題的處理邏輯消别。
一般遞歸的形式如下：
public void fun(factor){
if(end){
//end就是遞歸的結(jié)束條件
//directResolve()就是直接求解表達(dá)式抛蚤，在很多時候我們僅僅是想要終止遞歸台谢，并不需要子問題返回值，所以這時候可以沒有直接求解表達(dá)式岁经，直接return
directResolve();
}else{
//這就是歸納項朋沮，對于本次遞歸我們要處理的邏輯
doSomething(factor);
//這個就是不進(jìn)表達(dá)式，通過不斷改變factor的值來使遞歸向著終止條件靠近
factor=move(factor);
//調(diào)用自身缀壤，實現(xiàn)遞歸
fun(factor);
}
}
遞歸的例子
舉個最簡單的例子樊拓，那就不得不說求N的階乘
public static int factorial(int n){
//n就是步進(jìn)因子
if(n == 1){
//n==1是遞歸終止條件
//return 1是直接求解表達(dá)式
return 1;
}
//以下這一句n-1是步進(jìn)表達(dá)式
//n*factorial(n-1)是歸納項
//這就是為什么上面說歸納項和步進(jìn)表達(dá)式經(jīng)常在一起
return n * factorial(n - 1);
}
通過上面的例子，我們可以總結(jié)出來可以使用遞歸處理的問題的一些共同特征：
- 可以把該問題逐步分解為一個個的小問題塘慕，而且這些小問題與原問題有相同的結(jié)構(gòu)或者說表述
- 存在某種條件筋夏，使得問題不能繼續(xù)分解，并且在該條件下問題可以得到非常容易的解決图呢。
只要滿足著兩個條件条篷，就可以采用遞歸的辦法來解決
接下來舉一個比較復(fù)雜的問題：
有這么一個數(shù)據(jù)，全部由數(shù)字構(gòu)成蛤织，比如字符串"123456",或者整形123456赴叹，甚至可以是數(shù)組[1,2,3,4,5,6]（為了演示的方便，我把他當(dāng)做字符串）指蚜。任意刪除其中的T位乞巧，比如刪除其中的兩位，剩余的數(shù)字按照原來的順序排列摊鸡，求一個算法绽媒，使得刪除之后的數(shù)字的值最小。
比如"123456",可以刪除3和6,得到"1245",也可以刪除1和2免猾，得到"3456"是辕，我們要求得刪除之后最小的那個數(shù)，這里為"1234"掸刊。
就這樣一個問題免糕，網(wǎng)上有很多的解法，這里我說一下遞歸的解法。
這個問題可以概括為：一個N位數(shù)字石窑，刪除T位牌芋，剩余的按原來的順序求值，求剩余數(shù)字的最小值松逊。
按照遞歸的思路躺屁，求N位數(shù)字，刪除T位经宏，可以先求出N-1位數(shù)字刪除T-1位犀暑，求出最小值，然后N-2位刪除T-2位烁兰，求出最小值耐亏，一次類推，當(dāng)N=0或者T=0的時候結(jié)束遞歸沪斟。
按照上面思路給出代碼:
public static String findMin(String value, int T){
final int N = value.lenght();
if(N<=T||N<=0||T<=0){
//這是遞歸終止條件
return value;
}
String result = value;
for(int i = 0;i<N;i++){
//一次刪除value中的每一位广辰，其余的位數(shù)按原來的順序組合，得到一個N-1位的數(shù)字主之，然后遞歸求出這N-1位刪除T-1的最小值
String tmp = value.subString(0,i)+value.subString(i+1,N);
String temResult = findMin(tmp,T-1);
if(Integer.valueOf(result)>Integer.valueOf(tmpResult)){
result = tmpResult;
}
}
return result;
}
這個的思想是每次遞歸都找到最小的择吊，當(dāng)T減小到0的時候就正好可以求出刪除T位的時候最小數(shù)字。
比如槽奕，當(dāng)value為"312456",T為2時几睛，返回"1245"
這也是遞歸和循環(huán)結(jié)合使用的一個比較不錯的例子
有一個二分查找法，也是遞歸比較經(jīng)典的使用粤攒。
題目就不說了所森，現(xiàn)在來說一下它的解法思想：把已經(jīng)排序好的要查找的數(shù)字二分，比較中間數(shù)字與目標(biāo)的大小琼讽，如果中間數(shù)字比目標(biāo)大必峰，則說明要查找的在前一部分，然后繼續(xù)對前一部分使用相同的辦法钻蹬，下面來寫一下方法吼蚁。
//假設(shè)data已經(jīng)排序過了,如果找到了，就返回該key第一次出現(xiàn)的位置问欠，否則返回-1
public static int binarySearch(int[] data, int start, int end, int key){
int mid = (start+end)/2;
final int N = data.length;
if(end<=start){
//遞歸終止條件
if(data[start] == key){
return mid;
}else{
return -1;
}
}
//歸納項
if(data[mid]>key){
return binarySearch(data,start,mid,key);
}else if(data[mid]<key){
return binarySearch(data,mid+1,end,key);
}else{
return mid;
}
}
}
上半部分就說到這里肝匆。下一部分說一下 遞歸，迭代和循環(huán)顺献，以及尾遞歸的問題
