原來在學(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)顺献,以及尾遞歸的問題