五、如何遞，怎樣歸？

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

      所謂如何傳遞，我覺(jué)得思維的難點(diǎn)是如何抽象出數(shù)學(xué)模型，如果是斐波那契數(shù)列那種有明確公式的話，很簡(jiǎn)單，直接按照公式該怎么操作怎么操作，難得是只有敘述性語(yǔ)言的，比如這種題目：有一段樓梯n個(gè)階梯，你可以選擇一次上一個(gè)階梯，也可以選擇一次上兩個(gè)階梯，請(qǐng)問(wèn)走到頂部一共有多少種走法？看似很高深吧？其實(shí)這就是斐波那契數(shù)列的一個(gè)變體而已。這種描述性的題目如果要抽象出數(shù)學(xué)模型，我覺(jué)得***的辦法就先列舉幾個(gè)試試，先看看有什么規(guī)律沒(méi)有，然后再猜想，再證明。你先看看你上2層樓梯有幾種方法，2層樓梯要么是1次性上去，要么分成兩步，一次性上一步，于是就是F（2）=2，如果只有一層和沒(méi)有呢，那明顯只有一種走法(一次上一層和不走），也就是F(0)=1,F(1)=1,下面，你要上第三層，你的辦法要么是從第二層上一層到第三層，要么是在***層上兩層到第三層，要么一層一層的走上去，這樣F(3)=3，看起來(lái)還是沒(méi)有什么規(guī)律，接著往下來(lái)，現(xiàn)在要上第四層了，那么讓我們換一種思維方式，怎樣到第四層呢？要么你在第三層到第四層，要么從第二層到第四層，為什么不說(shuō)從***層到第四層呢？因?yàn)槿绻惆堰@個(gè)當(dāng)作一種情況的話，你會(huì)發(fā)現(xiàn)在***層的時(shí)候，無(wú)論下一步你怎樣做都會(huì)回到上面兩種情況之中。所以到第四層的作法就是F(3)+F(2),因?yàn)槟愕搅说谌龑踊蛘叩搅说诙樱ㄈ绻阍诘诙舆x擇上一層那么就會(huì)和在第三層的走法重合），后面的走法就確定了，不同的是前面的走法，也就是F(4)=5，現(xiàn)在讓我們?cè)黾狱c(diǎn)難度，如果你要到第n層，那么應(yīng)該說(shuō)***一步你有可能是從第n-1層走兩層上來(lái)的，也有可能是從第n層走兩層上來(lái)的，也就是說(shuō)到第n層的走法決定于你怎么走到第n-1層和第n層的，所以這個(gè)走法應(yīng)該是F(n)=F(n-1)+F(n-2)。

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

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

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

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

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

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

六、“高帥富”的裝備

      如果你看過(guò)一些時(shí)間復(fù)雜度可以到O(NLOGN）的排序算法，可以看到它們不僅效率高，代碼也很簡(jiǎn)潔，因?yàn)槭褂眠f歸使得很多復(fù)雜的過(guò)程變得簡(jiǎn)單，使得某個(gè)算法可以更容易的實(shí)現(xiàn)出來(lái)，我先要說(shuō)的是歸并排序。

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

如　設(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 ]  　

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

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

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

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

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

1.   left最開(kāi)始等于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í)行，到此步，輸出了三個(gè)0

1.2.1  left等于0，right等于center等于1，執(zhí)行MergeSort(numbers,tmpArray,left,center);下一行語(yǔ)句，輸出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);下面的語(yǔ)句，輸出2，然后進(jìn)入

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

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

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

【編輯推薦】