數據結構和演算法（八）：遞歸

06-04

數據結構和演算法（八）：遞歸

1、遞歸的定義

2、求一個數的階乘：n!

3、遞歸的二分查找

4、分治演算法

5、漢諾塔問題

5、歸併排序

6、消除遞歸

　　遞歸和棧

7、遞歸的有趣應用

　　①、求一個數的乘方

　　②、背包問題

　　③、組合：選擇一支隊伍

8、總結

　　記得小時候經常講的一個故事：從前有座山，山上有座廟，廟裡有一個老和尚和一個小和尚，一天，老和尚給小和尚講了一個故事，故事內容是「從前有座山，山上有座廟，廟裡有一個老和尚和一個小和尚，一天，老和尚給小和尚講了一個故事，故事內容......」

　　什麼是遞歸，上面的小故事就是一個明顯的遞歸。以編程的角度來看，程序調用自身的編程技巧稱為遞歸（ recursion）。

　　百度百科中的解釋是這樣的：遞歸做為一種演算法在程序設計語言中廣泛應用。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。

正文：

1、遞歸的定義

遞歸就是在運行的過程中調用自己。

遞歸必須要有三個要素：

　　①、邊界條件

　　②、遞歸前進段

　　③、遞歸返回段

當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

2、求一個數的階乘：n!

n! = n*(n-1)*(n-2)*......1

規定：

　　①、0！=1

　　②、1！=1

　　③、負數沒有階乘

上面的表達式我們先用for循環改寫：

/** * 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;}

　　如果求階乘的表達式是這樣的呢？

n! = n*(n-1)！

　　我們用遞歸來改寫：

/** * 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 * @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;}

　　二分查找用遞歸來改寫，相信也很簡單。邊界條件是找到當前值，或者查找範圍為空。否則每一次查找都將範圍縮小一半。

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上。

/** * 漢諾塔問題 * @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為中介塔座 }}

　　測試：

move(3,"A","B","C");

　　列印結果為：

5、歸併排序

　　歸併演算法的中心是歸併兩個已經有序的數組。歸併兩個有序數組A和B，就生成了第三個有序數組C。數組C包含數組A和B的所有數據項。

　　非遞歸演算法為：

/** * 傳入兩個有序數組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()方法將數組的兩半歸併成為一個有序的數組。如何來為每一部分排序呢？這裡我們利用遞歸的思想：

　　把每一半都分為四分之一，對每個四分之一進行排序，然後把它們歸併成一個有序的一半。類似的，如何給每個四分之一數組排序呢？把每個四分之一分成八分之一，對每個八分之一進行排序，以此類推，反覆的分割數組，直到得到的子數組是一個數據項，那這就是這個遞歸演算法的邊界值，也就是假定一個數據項的元素是有序的。

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]; }}

　　測試：

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。

x^y= (x^2)^(y/2)，定義a=x^2,b=y/2, 則得到形如： x^y= a^b;

　　具體演算法：

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 磅。但是如果讓計算機來解決這個問題，就需要給計算機設定詳細的指令了。

　　演算法如下：

　　一、如果在這個過程的任何時刻，選擇的數據項的總和符合目標重量，那麼工作便完成了。

　　二、從選擇的第一個數據項開始，剩餘的數據項的加和必須符合背包的目標重量減去第一個數據項的重量，這是一個新的目標重量。

　　三、逐個的試每種剩餘數據項組合的可能性，但是注意不要去試所有的組合，因為只要數據項的和大於目標重量的時候，就停止添加數據。

　　四、如果沒有合適的組合，放棄第一個數據項，並且從第二個數據項開始再重複一遍整個過程。

　　五、繼續從第三個數據項開始，如此下去直到你已經試驗了所有的組合，這時才知道有沒有解決方案。

　　具體實現過程：

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)，以此類推，很容易想到遞歸的思想。

　　具體實現代碼：

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); }}