五、如何遞，怎樣歸？

     很多人看完遞歸的原理之后會有這種感覺，喔，這個原理我懂了，然后再找一道其余的題目看一看能不能寫的出來，突然發(fā)現(xiàn)，我勒個去，還是不會。其實這種現(xiàn)象很普遍，所以如果你是這種的，也沒有什么好沮喪的，我敢保證你能看的懂遞歸的執(zhí)行過程，基本上已經(jīng)比30%的人要強(qiáng)了。所以我覺得，我寫一寫我對遞歸思維的理解好了。遞歸這個詞我的理解應(yīng)該是傳遞和回歸，如何把自身的狀態(tài)傳遞下去和如何回歸到一個結(jié)果上是遞歸問題的基本思維方式。

      所謂如何傳遞，我覺得思維的難點是如何抽象出數(shù)學(xué)模型，如果是斐波那契數(shù)列那種有明確公式的話，很簡單，直接按照公式該怎么操作怎么操作，難得是只有敘述性語言的，比如這種題目：有一段樓梯n個階梯，你可以選擇一次上一個階梯，也可以選擇一次上兩個階梯，請問走到頂部一共有多少種走法？看似很高深吧？其實這就是斐波那契數(shù)列的一個變體而已。這種描述性的題目如果要抽象出數(shù)學(xué)模型，我覺得***的辦法就先列舉幾個試試，先看看有什么規(guī)律沒有，然后再猜想，再證明。你先看看你上2層樓梯有幾種方法，2層樓梯要么是1次性上去，要么分成兩步，一次性上一步，于是就是F（2）=2，如果只有一層和沒有呢，那明顯只有一種走法(一次上一層和不走），也就是F(0)=1,F(1)=1,下面，你要上第三層，你的辦法要么是從第二層上一層到第三層，要么是在***層上兩層到第三層，要么一層一層的走上去，這樣F(3)=3，看起來還是沒有什么規(guī)律，接著往下來，現(xiàn)在要上第四層了，那么讓我們換一種思維方式，怎樣到第四層呢？要么你在第三層到第四層，要么從第二層到第四層，為什么不說從***層到第四層呢？因為如果你把這個當(dāng)作一種情況的話，你會發(fā)現(xiàn)在***層的時候，無論下一步你怎樣做都會回到上面兩種情況之中。所以到第四層的作法就是F(3)+F(2),因為你到了第三層或者到了第二層（如果你在第二層選擇上一層那么就會和在第三層的走法重合），后面的走法就確定了，不同的是前面的走法，也就是F(4)=5，現(xiàn)在讓我們增加點難度，如果你要到第n層，那么應(yīng)該說***一步你有可能是從第n-1層走兩層上來的，也有可能是從第n層走兩層上來的，也就是說到第n層的走法決定于你怎么走到第n-1層和第n層的，所以這個走法應(yīng)該是F(n)=F(n-1)+F(n-2)。

      還有一種不知道如何傳遞是不知道怎樣將遞歸算法轉(zhuǎn)換成程序，你知道怎樣用語言描述出遞歸，但是就是不知道怎樣用程序描寫出來，所以***的方式是找一段遞歸的程序，然后看他每一次遞歸的輸出。

     關(guān)于如何歸，就是要找到遞歸中止的條件，比如斐波那契數(shù)列那個，n=0就是數(shù)列的中止條件，別小看這個中止條件，如果不能找出這個中止條件或者定義錯誤的話，后果就是無限的遞歸，導(dǎo)致程序堆棧的崩潰，最終整個程序就很快的崩潰掉了。

     我們從一個簡單的開始，使用遞歸算法求***公約數(shù)，利用輾轉(zhuǎn)相除法,簡單的說就是對于兩個數(shù)m和n，利用公式gcd（m,n)=gcd(n,m%n)=

gcd(m%n,m%n%n),直到后面的余數(shù)為0為止，這是個有數(shù)學(xué)公式的比較明顯的遞歸模式，所以按照這個數(shù)學(xué)公式的邏輯，這個遞歸算法的回歸的話n==0的時候，所以這個算法很容易寫出來。

     代碼相當(dāng)?shù)暮唵?，思路要很清晰。那么，再來看一個二分搜索的好了，二分搜索是在已經(jīng)排序好的數(shù)列里面尋找目標(biāo)數(shù)，比如{1,2,...,10},這種，如果是尋找2，那么先求出這一組數(shù)的中值5，2比5小，從而轉(zhuǎn)到0-5這個部分，其中值是2,然后就找到了。這種搜索的過程也是一種不斷傳遞的過程，將某個數(shù)列的中值和要查找的目標(biāo)值比較，如果比它小，就在數(shù)列的后半部分做同樣的操作，如果比它大，就在前半部分做相同的操作。那么這個回歸的條件是什么呢？應(yīng)該說有兩個，一個是找到了，也就是某一個中值等于目標(biāo)值，一個是沒有找到，可以定義為找到了***個元素和***一個元素還是沒有找到，那么也結(jié)束遞歸，其代碼如下:

int BinarySearch(int a[],int n,int low,int high) 
 { 
     int mid=(low+high)/2; 
     if(n==a[mid]) 
         return mid; 
     if((mid==high||mid==low)&&n!=a[mid]) 
         return 0; 
  
     if(n>a[mid]) 
           BinarySearch(a,n,mid+1,high); 
     else  
           BinarySearch(a,n,low,mid); 
       
 } 

     通過代碼可以看到思路和我上面語言描述的基本是一致的，這就是遞歸的好處，可以使得代碼更加清晰。

六、“高帥富”的裝備

      如果你看過一些時間復(fù)雜度可以到O(NLOGN）的排序算法，可以看到它們不僅效率高，代碼也很簡潔，因為使用遞歸使得很多復(fù)雜的過程變得簡單，使得某個算法可以更容易的實現(xiàn)出來，我先要說的是歸并排序。

     歸并排序簡單的將就是將一個數(shù)列不斷的平均分為兩個小數(shù)列，然后每個小數(shù)列獨立排序之后再合并在一起排序，也就是用若干有序的子序列得到一個有序的數(shù)列，為了說明，還是用一個例子好了，就用百度的這個例子好了：

如　設(shè)有數(shù)列{6，202，100，301，38，8，1}

初始狀態(tài)： [6] [202] [100] [301] [38] [8] [1]

            　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　 　　

                  i=2 [ 6 100 202 301 ] [ 1 8 38 ]　

            　　i=3　[ 1 6 8 38 100 202 301 ]  　

       整個過程就是不斷的劃分為子序列，不斷的用子序列排序，這明顯是一個遞歸的過程，傳遞的過程是不斷傳遞子序列，那么回歸條件是什么呢？貌似這里不太能夠看出來，從上面的過程可以大概看出來如果當(dāng)數(shù)列的個數(shù)只有1的話，那么就要開始回歸了，所以我們采用了一個方法，既然需要找中間的那個值，那么就要保存左邊的索引和右邊的索引，利用這兩個索引，可以確定出數(shù)組中有多少個值，那么先看一下代碼吧。

void MergeSort(int numbers[],int array_size) 
{ 
    int* tmpArray =new int[array_size-1]; 
    MergeSort(numbers,tmpArray,0,array_size-1); 
 
} 
 
void MergeSort(int numbers[],int tmpArray[],int left,int right) 
{ 
    if(left<right) 
    { 
        int center=(left+right)/2; 
        cout<<"0"<<endl; 
        MergeSort(numbers,tmpArray,left,center); 
        cout<<"1"<<endl; 
        MergeSort(numbers,tmpArray,center+1,right); 
        cout<<"2"<<endl; 
        Merge(numbers,tmpArray,left,center+1,right); 
        cout<<"3"<<endl; 
    } 
} 
 
void Merge(int numbers[],int tmpArray[],int leftPos,int rightPos,int rightEnd) 
{ 
    int leftEnd=rightPos-1; 
    int tmpPos=leftPos; 
    int numElements=rightEnd-leftPos+1; 
 
    while(leftPos<=leftEnd&&rightPos<=rightEnd) 
    { 
        if(numbers[leftPos]<=numbers[rightPos]) 
            tmpArray[tmpPos++]=numbers[leftPos++]; 
        else 
            tmpArray[tmpPos++]=numbers[rightPos++]; 
    } 
    while(leftPos<=leftEnd) 
         tmpArray[tmpPos++]=numbers[leftPos++]; 
    while(rightPos<=rightEnd) 
         tmpArray[tmpPos++]=numbers[rightPos++]; 
 
    for(int i=0;i<numElements;i++,rightEnd--) 
         numbers[rightEnd]=tmpArray[rightEnd]; 
         
    for (int i = 0; i < numElements; i++){ 
            cout<<numbers[i]<<" "; 
        } 
        cout<<endl; 
} 

      代碼開始有些復(fù)雜了，真正有點算法的感覺了，先看看三個函數(shù)，***個函數(shù)沒有什么特別的含義，只是屏蔽掉一些細(xì)節(jié)而已，從第二個MergeSort開始，可以看到就像我們描述的思路那樣，***個是比較是否數(shù)組里只有一個值，需要回歸啦，然后求出中值，左邊的排序成有序的子序列，然后排序右邊的，***將兩個子序列合并起來，是不是思路特別的清晰？那么接下來看看Merge函數(shù)，如果有兩個有序的子序列如何將他們合并成一個？因為這兩個子序列都是有序的，記為子序列A和子序列B，A[0]到A[size-1]是有序的，B[0]到B[size-1]也是有序的，那么對比的過程就簡單了，不斷的對比不斷的合并就可以了。

      對于函數(shù)執(zhí)行的遞歸過程，肯定很多人還是一頭霧水，這很正常，畢竟沒有一個清晰的直觀的認(rèn)識，那么讓我們看看遞歸的每一步都是怎么走的吧。

      對于百度給的那個例子，從頭看起，我們調(diào)用的代碼是 MergeSort(a,7); 所以，

1.   left最開始等于0，right等于6，進(jìn)入MergeSort以后left<right，進(jìn)入if，輸出0，center=3，調(diào)用   MergeSort(numbers,tmpArray,left,center);
1.1 left等于0，right等于center等于3，依然滿足left<right，進(jìn)入if，輸出0，center=1，繼續(xù)調(diào)用   MergeSort(numbers,tmpArray,left,center);

1.2 left等于0，right等于center等于1，依然滿足left<right，進(jìn)入if，輸出0，center=0，繼續(xù)調(diào)用   MergeSort(numbers,tmpArray,left,center);

1.3 left等于0，right等于center等于0，不滿足left<right，掉回1.2往下執(zhí)行，到此步，輸出了三個0

1.2.1  left等于0，right等于center等于1，執(zhí)行MergeSort(numbers,tmpArray,left,center);下一行語句，輸出1，執(zhí)行       MergeSort(numbers,tmpArray,center+1,right);

1.2.2 left等于center+1等于1，right=1，不滿足left<right,回到1.2.1,執(zhí)行MergeSort(numbers,tmpArray,center+1,right);下面的語句，輸出2，然后進(jìn)入

 Merge(numbers,tmpArray,left,center+1,right);排序完成之后輸出3。

       以上是一次完整的遞歸過程，對著輸出可以看到這個過程的執(zhí)行，作為理解遞歸的練習(xí)，完全可以對照著后面的輸出熟悉遞歸的過程，對于遞歸的執(zhí)行，我覺得可以理解為執(zhí)行到調(diào)用自己的函數(shù)的時候就不斷的困在自己的這個函數(shù)中，直到到達(dá)某一個條件時，被自己釋放，回到上一個過程才能進(jìn)行，這個過程就像有的人失戀了，每天都和自己糾結(jié)，每天都在痛苦和不安中度過，這個過程中他是不能往下走的，一旦到某一個條件，比如時間慢慢的沖淡了感覺，他又可以繼續(xù)進(jìn)行了。

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/26/2704241.html

【編輯推薦】