Java数据结构和算法（八）——递归
記得小時候經常講的一個故事：從前有座山，山上有座廟，廟里有一個老和尚和一個小和尚，一天，老和尚給小和尚講了一個故事，故事內容是“從前有座山，山上有座廟，廟里有一個老和尚和一個小和尚，一天，老和尚給小和尚講了一個故事，故事內容......”
什么是遞歸，上面的小故事就是一個明顯的遞歸。以編程的角度來看，程序調用自身的編程技巧稱為遞歸（ recursion）。
百度百科中的解釋是這樣的：遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。
回到頂部
1、遞歸的定義
遞歸，就是在運行的過程中調用自己。
遞歸必須要有三個要素：
①、邊界條件
②、遞歸前進段
③、遞歸返回段
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
回到頂部
2、求一個數的階乘：n!
| 1 | n! = n*(n-1)*(n-2)*......1 |
規定：
①、0！=1
②、1！=1
③、負數沒有階乘
上面的表達式我們先用for循環改寫：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | /** ?* 0！=1? 1！=1 ?* 負數沒有階乘,如果輸入負數返回-1 ?* @param n ?* @return ?*/ public?static?int?getFactorialFor(int?n){ ????int?temp =?1; ????if(n >=0){ ????????for(int?i =?1?; i <= n ; i++){ ????????????temp = temp*i; ????????} ????}else{ ????????return?-1; ????} ????return?temp; } |
如果求階乘的表達式是這樣的呢？
| 1 | n! = n*(n-1)！ |
我們用遞歸來改寫：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /** ?* 0！=1? 1！=1 ?* 負數沒有階乘,如果輸入負數返回-1 ?* @param n ?* @return ?*/ public?static?int?getFactorial(int?n){ ????if(n >=?0){ ????????if(n==0){ ????????????System.out.println(n+"!=1"); ????????????return?1; ????????}else{ ????????????System.out.println(n); ????????????int?temp = n*getFactorial(n-1); ????????????System.out.println(n+"!="+temp); ????????????return?temp; ????????} ????} ????return?-1; } |
我們調用該方法getFactorial(4);即求4！打印如下：
這段遞歸程序的邊界條件就是n==0時，返回1，具體調用過程如下：
回到頂部
3、遞歸的二分查找
注意：二分查找的數組一定是有序的！！！
在有序數組array[]中，不斷將數組的中間值（mid）和被查找的值比較，如果被查找的值等于array[mid],就返回下標mid; 否則，就將查找范圍縮小一半。如果被查找的值小于array[mid], 就繼續在左半邊查找;如果被查找的值大于array[mid],? 就繼續在右半邊查找。 直到查找到該值或者查找范圍為空時， 查找結束。
不用遞歸的二分查找如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** ?* 找到目標值返回數組下標，找不到返回-1 ?* @param array ?* @param key ?* @return ?*/ public?static?int?findTwoPoint(int[] array,int?key){ ????int?start =?0; ????int?last = array.length-1; ????while(start <= last){ ????????int?mid = (last-start)/2+start;//防止直接相加造成int范圍溢出 ????????if(key == array[mid]){//查找值等于當前值，返回數組下標 ????????????return?mid; ????????} ????????if(key > array[mid]){//查找值比當前值大 ????????????start = mid+1; ????????} ????????if(key < array[mid]){//查找值比當前值小 ????????????last = mid-1; ????????} ????} ????return?-1; } |
二分查找用遞歸來改寫，相信也很簡單。邊界條件是找到當前值，或者查找范圍為空。否則每一次查找都將范圍縮小一半。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | public?static?int?search(int[] array,int?key,int?low,int?high){ ????int?mid = (high-low)/2+low; ????if(key == array[mid]){//查找值等于當前值，返回數組下標 ????????return?mid; ????}else?if(low > high){//找不到查找值，返回-1 ????????return?-1; ????}else{ ????????if(key < array[mid]){//查找值比當前值小 ????????????return?search(array,key,low,mid-1); ????????} ????????if(key > array[mid]){//查找值比當前值大 ????????????return?search(array,key,mid+1,high); ????????} ????} ????return?-1; } |
遞歸的二分查找和非遞歸的二分查找效率都為O(logN)，遞歸的二分查找更加簡潔，便于理解，但是速度會比非遞歸的慢。
回到頂部
4、分治算法
當我們求解某些問題時，由于這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對于這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。
上面講的遞歸的二分查找法就是一個分治算法的典型例子，分治算法常常是一個方法，在這個方法中含有兩個對自身的遞歸調用，分別對應于問題的兩個部分。
二分查找中，將查找范圍分成比查找值大的一部分和比查找值小的一部分，每次遞歸調用只會有一個部分執行。
回到頂部
5、漢諾塔問題
漢諾塔問題是由很多放置在三個塔座上的盤子組成的一個古老的難題。如下圖所示，所有盤子的直徑是不同的，并且盤子中央都有一個洞使得它們剛好可以放在塔座上。所有的盤子剛開始都放置在A 塔座上。這個難題的目標是將所有的盤子都從塔座A移動到塔座C上，每次只可以移動一個盤子，并且任何一個盤子都不可以放置在比自己小的盤子之上。
試想一下，如果只有兩個盤子，盤子從小到大我們以數字命名（也可以想象為直徑），兩個盤子上面就是盤子1，下面是盤子2，那么我們只需要將盤子1先移動到B塔座上，然后將盤子2移動到C塔座，最后將盤子1移動到C塔座上。即完成2個盤子從A到C的移動。
如果有三個盤子，那么我們將盤子1放到C塔座，盤子2放到B塔座，在將C塔座的盤子1放到B塔座上，然后將A塔座的盤子3放到C塔座上，然后將B塔座的盤子1放到A塔座，將B塔座的盤子2放到C塔座，最后將A塔座的盤子1放到C塔座上。
如果有四個，五個，N個盤子，那么我們應該怎么去做？這時候遞歸的思想就很好解決這樣的問題了，當只有兩個盤子的時候，我們只需要將B塔座作為中介，將盤子1先放到中介塔座B上，然后將盤子2放到目標塔座C上，最后將中介塔座B上的盤子放到目標塔座C上即可。
所以無論有多少個盤子，我們都將其看做只有兩個盤子。假設有 N 個盤子在塔座A上，我們將其看為兩個盤子，其中(N-1)~1個盤子看成是一個盤子，最下面第N個盤子看成是一個盤子，那么解決辦法為：
①、先將A塔座的第(N-1)~1個盤子看成是一個盤子，放到中介塔座B上，然后將第N個盤子放到目標塔座C上。
②、然后A塔座為空，看成是中介塔座，B塔座這時候有N-1個盤子，將第(N-2)~1個盤子看成是一個盤子，放到中介塔座A上，然后將B塔座的第(N-1)號盤子放到目標塔座C上。
③、這時候A塔座上有(N-2)個盤子，B塔座為空，又將B塔座視為中介塔座，重復①，②步驟，直到所有盤子都放到目標塔座C上結束。
簡單來說，跟把大象放進冰箱的步驟一樣，遞歸算法為：
①、從初始塔座A上移動包含n-1個盤子到中介塔座B上。
②、將初始塔座A上剩余的一個盤子（最大的一個盤子）放到目標塔座C上。
③、將中介塔座B上n-1個盤子移動到目標塔座C上。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | /** ?* 漢諾塔問題 ?* @param dish 盤子個數(也表示名稱) ?* @param from 初始塔座 ?* @param temp 中介塔座 ?* @param to?? 目標塔座 ?*/ public?static?void?move(int?dish,String from,String temp,String to){ ????if(dish ==?1){ ????????System.out.println("將盤子"+dish+"從塔座"+from+"移動到目標塔座"+to); ????}else{ ????????move(dish-1,from,to,temp);//A為初始塔座，B為目標塔座，C為中介塔座 ????????System.out.println("將盤子"+dish+"從塔座"+from+"移動到目標塔座"+to); ????????move(dish-1,temp,from,to);//B為初始塔座，C為目標塔座，A為中介塔座 ????} } |
測試：
| 1 | move(3,"A","B","C"); |
打印結果為：
回到頂部
5、歸并排序
? 歸并算法的中心是歸并兩個已經有序的數組。歸并兩個有序數組A和B，就生成了第三個有序數組C。數組C包含數組A和B的所有數據項。
非遞歸算法為：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /** ?* 傳入兩個有序數組a和b，返回一個排好序的合并數組 ?* @param a ?* @param b ?* @return ?*/ public?static?int[] sort(int[] a,int[] b){ ????int[] c =?new?int[a.length+b.length]; ????int?aNum =?0,bNum =?0,cNum=0; ????while(aNum<a.length && bNum < b.length){ ????????if(a[aNum] >= b[bNum]){//比較a數組和b數組的元素，誰更小將誰賦值到c數組 ????????????c[cNum++] = b[bNum++]; ????????}else{ ????????????c[cNum++] = a[aNum++]; ????????} ????} ????//如果a數組全部賦值到c數組了，但是b數組還有元素，則將b數組剩余元素按順序全部復制到c數組 ????while(aNum == a.length && bNum < b.length){ ????????c[cNum++] = b[bNum++]; ????} ????//如果b數組全部賦值到c數組了，但是a數組還有元素，則將a數組剩余元素按順序全部復制到c數組 ????while(bNum == b.length && aNum < a.length){ ????????c[cNum++] = a[aNum++]; ????} ????return?c; } |
該方法有三個while循環，第一個while比較數組a和數組b的元素，并將較小的賦值到數組c；第二個while循環當a數組所有元素都已經賦值到c數組之后，而b數組還有元素，那么直接把b數組剩余的元素賦值到c數組；第三個while循環則是b數組所有元素都已經賦值到c數組了，而a數組還有剩余元素，那么直接把a數組剩余的元素全部賦值到c數組。
? 歸并排序的思想是把一個數組分成兩半，排序每一半，然后用上面的sort()方法將數組的兩半歸并成為一個有序的數組。如何來為每一部分排序呢？這里我們利用遞歸的思想：
把每一半都分為四分之一，對每個四分之一進行排序，然后把它們歸并成一個有序的一半。類似的，如何給每個四分之一數組排序呢？把每個四分之一分成八分之一，對每個八分之一進行排序，以此類推，反復的分割數組，直到得到的子數組是一個數據項，那這就是這個遞歸算法的邊界值，也就是假定一個數據項的元素是有序的。
?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | public?static?int[] mergeSort(int[] c,int?start,int?last){ ????if(last > start){ ????????//也可以是(start+last)/2，這樣寫是為了防止數組長度很大造成兩者相加超過int范圍，導致溢出 ????????int?mid = start + (last - start)/2; ????????mergeSort(c,start,mid);//左邊數組排序 ????????mergeSort(c,mid+1,last);//右邊數組排序 ????????merge(c,start,mid,last);//合并左右數組 ????} ????return?c; } ? public?static?void?merge(int[] c,int?start,int?mid,int?last){ ????int[] temp =?new?int[last-start+1];//定義臨時數組 ????int?i = start;//定義左邊數組的下標 ????int?j = mid +?1;//定義右邊數組的下標 ????int?k =?0; ????while(i <= mid && j <= last){ ????????if(c[i] < c[j]){ ????????????temp[k++] = c[i++]; ????????}else{ ????????????temp[k++] = c[j++]; ????????} ????} ????//把左邊剩余數組元素移入新數組中 ????while(i <= mid){ ????????temp[k++] = c[i++]; ????} ????//把右邊剩余數組元素移入到新數組中 ????while(j <= last){ ????????temp[k++] = c[j++]; ????} ????? ????//把新數組中的數覆蓋到c數組中 ????for(int?k2 =?0?; k2 < temp.length ; k2++){ ????????c[k2+start] = temp[k2]; ????} } |
測試：
| 1 2 3 | int[] c = {2,7,8,3,1,6,9,0,5,4}; c = mergeSort(c,0,c.length-1); System.out.println(Arrays.toString(c)); |
結果為：
回到頂部
6、消除遞歸
一個算法作為一個遞歸的方法通常通概念上很容易理解，但是遞歸的使用在方法的調用和返回都會有額外的開銷，通常情況下，用遞歸能實現的，用循環都可以實現，而且循環的效率會更高，所以在實際應用中，把遞歸的算法轉換為非遞歸的算法是非常有用的。這種轉換通常會使用到棧。
遞歸和棧
遞歸和棧有這緊密的聯系，而且大多數編譯器都是用棧來實現遞歸的，當調用一個方法時，編譯器會把這個方法的所有參數和返回地址都壓入棧中，然后把控制轉移給這個方法。當這個方法返回時，這些值退棧。參數消失了，并且控制權重新回到返回地址處。
調用一個方法時所發生的事：
一、當一個方法被調用時，它的參數和返回地址被壓入一個棧中；
二、這個方法可以通過獲取棧頂元素的值來訪問它的參數；
三、當這個方法要返回時，它查看棧以獲得返回地址，然后這個地址以及方法的所有參數退棧，并且銷毀。
回到頂部
7、遞歸的有趣應用
①、求一個數的乘方
一般稍微復雜一點的計算器上面都能求一個數的乘法，通常計算器上面的標志是 x^y 這樣的按鍵，表示求 x 的 y 次方。一般情況下我們是如何求一個數的乘法的呢？
比如2^8,我們可以會求表達式2*2*2*2*2*2*2*2 的值，但是如果y的值很大，這個會顯得表達式很冗長。那么由沒有更快一點方法呢？
數學公式如下是成立的：
(Xa)b?= Xa*b
如果如果求28次方，我們可以先假定22=a,于是28?= （22）4?，那么就是a4?；假定 a2?= b，那么 a4?= b2，而b2可以寫成(b2)1。于是現在28就轉換成：b*b
也就是說我們將乘方的運算轉換為乘法的運算。
求xy的值，當y是偶數的時候，最后能轉換成兩個數相乘，當時當y是奇數的時候，最后我們必須要在返回值后面額外的乘以一個x。
| 1 | x^y= (x^2)^(y/2)，定義a=x^2,b=y/2, 則得到形如： x^y= a^b; |
具體算法：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public?static?int?pow(int?x,int?y){ ????if(x ==?0?|| x ==?1){ ????????return?x; ????} ????if(y >?1){ ????????int?b = y/2; ????????int?a = x*x; ????????if(y%2?==?1){//y為奇數 ????????????return?pow(a,b)*x; ????????}else{//y為偶數 ????????????return?pow(a,b); ????????} ????}else?if(y ==?0){ ????????return?1; ????}else{//y==1 ????????return?x; ????} } |
②、背包問題
? 背包問題也是計算機中的經典問題。在最簡單的形式中，包括試圖將不同重量的數據項放到背包中，以使得背包最后達到指定的總重量。
比如：假設想要讓背包精確地承重20磅，并且有 5 個可以放入的數據項，它們的重量分別是 11 磅，8 磅，7 磅，6 磅，5 磅。這個問題可能對于人類來說很簡單，我們大概就可以計算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果讓計算機來解決這個問題，就需要給計算機設定詳細的指令了。
算法如下：
一、如果在這個過程的任何時刻，選擇的數據項的總和符合目標重量，那么工作便完成了。
二、從選擇的第一個數據項開始，剩余的數據項的加和必須符合背包的目標重量減去第一個數據項的重量，這是一個新的目標重量。
三、逐個的試每種剩余數據項組合的可能性，但是注意不要去試所有的組合，因為只要數據項的和大于目標重量的時候，就停止添加數據。
四、如果沒有合適的組合，放棄第一個數據項，并且從第二個數據項開始再重復一遍整個過程。
五、繼續從第三個數據項開始，如此下去直到你已經試驗了所有的組合，這時才知道有沒有解決方案。
具體實現過程：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | package?com.ys.recursion; ? public?class?Knapsack { ????private?int[] weights;?//可供選擇的重量 ????private?boolean[] selects;?//記錄是否被選擇 ????? ????public?Knapsack(int[] weights){ ????????this.weights = weights; ????????selects =?new?boolean[weights.length]; ????} ????? ????/** ?????* 找出符合承重重量的組合 ?????* @param total 總重量 ?????* @param index 可供選擇的重量下標 ?????*/ ????public?void?knapsack(int?total,int?index){ ????????if(total <?0?|| total >?0?&& index >= weights.length){ ????????????return;//沒找到解決辦法，直接返回 ????????} ????????if(total ==?0){//總重量為0，則找到解決辦法了 ????????????for(int?i =?0?; i < index ; i++){ ????????????????if(selects[i] ==?true){ ????????????????????System.out.println(weights[i]+" "); ????????????????} ????????????} ????????????System.out.println(); ????????????return; ????????} ????????selects[index] =?true; ????????knapsack(total-weights[index], index+1); ????????selects[index] =?false; ????????knapsack(total, index+1); ????} ????? ????public?static?void?main(String[] args) { ????????int?array[] = {11,9,7,6,5}; ????????int?total =?20; ????????Knapsack k =?new?Knapsack(array); ????????k.knapsack(total,?0); ????} ? } |
③、組合：選擇一支隊伍
在數學中，組合是對事物的一種選擇，而不考慮他們的順序。
比如有5個登山隊員，名稱為 A,B,C,D和E。想要從這五個隊員中選擇三個隊員去登峰，這時候如何列出所有的隊員組合。（不考慮順序）
還是以遞歸的思想來解決：首先這五個人的組合選擇三個人分成兩個部分，第一部分包含A隊員，第二部分不包含A隊員。假設把從 5 個人中選出 3 個人的組合簡寫為（5,3），規定 n 是這群人的大小，并且 k 是組隊的大小。那么根據法則可以有：
(n,k) = (n-1,k-1) + (n-1,k)
? 對于從 5 個人中選擇 3 個人，有：
(5,3) = (4,2)+(4,3)
(4,2)表示已經有A隊員了，然后從剩下的4個隊員中選擇2個隊員，(4,3)表示從5個人中剔除A隊員，從剩下的4個隊員中選擇3個隊員，這兩種情況相加就是從5個隊員中選擇3個隊員。
現在已經把一個大問題轉換為兩個小問題了。從4個人的人群中做兩次選擇（一次選擇2個，一次選擇3個），而不是從5個人的人群中選擇3個。
從4個人的人群中選擇2個人，又可以表示為：(4,2) = (3,1) + (3,2)，以此類推，很容易想到遞歸的思想。
具體實現代碼：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | package?com.ys.recursion; ? public?class?Combination { ????private?char[] persons;//組中所有可供選擇的人員 ????private?boolean[] selects;//標記成員是否被選中，選中為true ????? ????public?Combination(char[] persons){ ????????this.persons = persons; ????????selects =?new?boolean[persons.length]; ????} ????public?void?showTeams(int?teamNumber){ ????????combination(teamNumber,0); ????} ????/** ?????* ?????* @param teamNumber 需要選擇的隊員數 ?????* @param index 從第幾個隊員開始選擇 ?????*/ ????public?void?combination(int?teamNumber,int?index){ ????????if(teamNumber ==?0){//當teamNumber=0時，找到一組 ????????????for(int?i =?0?; i < selects.length ; i++){ ????????????????if(selects[i] ==?true){ ????????????????????System.out.print(persons[i]+" "); ????????????????} ????????????} ????????????System.out.println(); ????????????return; ????????} ????????//index超過組中人員總數，表示未找到 ????????if(index >= persons.length ){ ????????????return; ????????} ????????selects[index] =?true; ????????combination(teamNumber-1, index+1); ????????selects[index] =?false; ????????combination(teamNumber, index+1); ????} ? ????public?static?void?main(String[] args) { ????????char[] persons = {'A','B','C','D','E'}; ????????Combination cb =?new?Combination(persons); ????????cb.showTeams(3); ????} } |
回到頂部
8、總結
一個遞歸方法每次都是用不同的參數值反復調用自己，當某種參數值使得遞歸的方法返回，而不再調用自身，這種情況稱為邊界值，也叫基值。當遞歸方法返回時，遞歸過程通過逐漸完成各層方法實例的未執行部分，而從最內層返回到最外層的原始調用處。
階乘、漢諾塔、歸并排序等都可以用遞歸來實現，但是要注意任何可以用遞歸完成的算法用棧都能實現。當我們發現遞歸的方法效率比較低時，可以考慮用循環或者棧來代替它。
作者：YSOcean
出處：http://www.cnblogs.com/ysocean/
總結
以上是生活随笔為你收集整理的Java数据结构和算法（八）——递归的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java数据结构和算法（六）——前缀、中
- 下一篇： Java数据结构和算法（十）——二叉树