遞歸和分治思想

如果可以使用迭代，盡量別使用遞歸。由編譯原理可以知道，每次自調(diào)用的時(shí)候，計(jì)算機(jī)都需要保存在調(diào)用，浪費(fèi)時(shí)間空間。當(dāng)然，迭代是當(dāng)我們知道循環(huán)次數(shù)的時(shí)候。而當(dāng)我們不知道循環(huán)次數(shù)，比如說(shuō)對(duì)于文件夾和文件進(jìn)行遍歷，不知道深度的情況下，我們就需要遞歸來(lái)實(shí)現(xiàn)。

顯然，遞歸是先解決小的問(wèn)題，這種思想是分治思想。根據(jù)具體需求，來(lái)決定是否使用遞歸。

遞歸要注意：

  • 結(jié)構(gòu)是選擇結(jié)構(gòu)，而迭代是循環(huán)結(jié)構(gòu)

  • 必須有基線條件和遞歸條件，防止出現(xiàn)死循環(huán)

  • 如果知道循環(huán)次數(shù)的話，盡量使用遞歸

  • 對(duì)于某些編程式函數(shù)，有對(duì)于尾遞歸的迭代優(yōu)化

  • 遞歸邏輯更容易理解

一些實(shí)例

逆序輸出字符串

#include<iostream>using namespace std;void print(){    char a;    cin>>a;    if(a!='#') print(); // 不是停止符，先自調(diào)用 
    if(a!='#') cout<<a; //在回來(lái)的時(shí)候，打印自己的字符 }int main(){
    print();    return 0;
}

查找數(shù)組元祖是否存在

很多時(shí)候我們需要查找一個(gè)數(shù)組中是否有一個(gè)元素。如果使用迭代，肯定十分簡(jiǎn)單，時(shí)間復(fù)雜度為O(n)。

此時(shí)，如果使用分而治之的思想，我們可以使用二分法來(lái)進(jìn)行查找。不論多大的數(shù)據(jù)，時(shí)間復(fù)雜度顯著降低為O(log_2 n)。也就是說(shuō)一個(gè)大小為123456789的數(shù)組，使用迭代，我們需要123456789個(gè)時(shí)間單位。但是二分法只需要27次。

實(shí)現(xiàn)思路：

  1. 首先轉(zhuǎn)化的思想對(duì)數(shù)組進(jìn)行排序。如果不排序，那么low和high就沒(méi)有意義了。

  2. 再用迭代進(jìn)行二分

#include<iostream>#include<algorithm>using namespace std;const int SIZE = 5;const int NONE = -1;//二分查找并且返回element的位置，沒(méi)查找到則返回NONEtemplate<class T>int BinFind(T *arr,int low,int high,T elem){  
    int mid;    if(low>high)        return NONE;    else{
        mid = (low+high)/2;        if(arr[mid] == elem)            return mid;        else if(elem>arr[mid])            return BinFind(arr,mid+1,high,elem);        else
            return BinFind(arr,low,mid-1,elem);
    }
}int main(){    int *arr = new int [SIZE];    cout<<"請(qǐng)輸入"<<SIZE<<"個(gè)數(shù)據(jù)："; 
    for(int i=0;i<SIZE;++i)        cin>>arr[i];
    sort(arr,arr+SIZE);    int elem;    cout<<"輸入您要查找的數(shù)據(jù)："<<endl;    cin>>elem; 
    int index = BinFind(arr,0,SIZE-1,elem);    if (index+1)        cout<<"含有這個(gè)數(shù)據(jù)\n";    else
        cout<<"不含有這個(gè)數(shù)據(jù)";    return 0;
}

漢諾塔問(wèn)題

首先我們假設(shè)需要移動(dòng)64層，那么思路如下（附截圖）：

電腦培訓(xùn),計(jì)算機(jī)培訓(xùn),平面設(shè)計(jì)培訓(xùn),網(wǎng)頁(yè)設(shè)計(jì)培訓(xùn),美工培訓(xùn),Web培訓(xùn),Web前端開(kāi)發(fā)培訓(xùn)

此時(shí)，需要解決兩個(gè)問(wèn)題（附截圖）：

電腦培訓(xùn),計(jì)算機(jī)培訓(xùn),平面設(shè)計(jì)培訓(xùn),網(wǎng)頁(yè)設(shè)計(jì)培訓(xùn),美工培訓(xùn),Web培訓(xùn),Web前端開(kāi)發(fā)培訓(xùn)

一直這樣類(lèi)推，知道最后從begin(開(kāi)始柱子)->end(目標(biāo)柱子)。

按照第一張截圖，我們可以寫(xiě)出來(lái)函數(shù)里面else的遞歸部分。并且，每次輸出的時(shí)候，就對(duì)應(yīng)著思路里面的移動(dòng)（而不是分治），此時(shí)step步數(shù)需要加+。

#include<iostream>#include<algorithm>using namespace std;void Hanoi(int num,char begin,char by,char end,int &step){    if(num==1){        cout<<begin<<"-->"<<end<<endl;
        ++step;
    }    else{
        Hanoi(num-1,begin,end,by,step);        cout<<begin<<"-->"<<end<<endl;
        ++step;
        Hanoi(num-1,by,begin,end,step);
    }
}int main(){    int step = 0;    int num;    cout<<"漢諾塔層數(shù)是: ";    cin>>num;
    Hanoi(num,'X','Y','Z',step);    cout<<"一共有："<<step<<"步數(shù)"<<endl; 
    return 0;
}

八皇后問(wèn)題

在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。正規(guī)的方法是遞歸，如果不考慮效率，這里采用遞歸實(shí)現(xiàn)。假設(shè)從第一行開(kāi)始，每一行都找到符合條件的一個(gè)位置，而條件就是新的一行的新位置符合要求，以此類(lèi)推，就可以寫(xiě)出來(lái)遞歸函數(shù)。

#include<iostream>using namespace std;const int Q_NUM = 8;int queens[Q_NUM][Q_NUM] = {0};int RESULT = 0;void print(){    for(int i=0;i<Q_NUM;++i){        for (int j=0;j<Q_NUM;++j)            cout<<queens[i][j]<<" ";        cout<<endl;
    }    cout<<endl<<endl;
}bool IfQueen(int row,int col){    if(row==0){        //當(dāng)?shù)谝恍袝r(shí)候，隨便擺放 
        queens[row][col] = 1;        return true;
    }    /**************其他時(shí)候，需要考慮上面的同一列、左上角斜線、右上角斜線，以下分別實(shí)現(xiàn)*****/ 
    for(int i=0;i<row;++i)        if(queens[i][col]==1)            return false;    
    for (int i=row-1,j = col-1;i>=0 && j>=0;--i,--j)        if(queens[i][j]==1)            return false;    
    for(int i=row-1,j=col+1;i>=0 && j<Q_NUM;--i,++j)        if(queens[i][j]==1)            return false;    
    /******當(dāng)所有情況都滿足********/
    queens[row][col] = 1;    return true;
}void Queen(int row){    if(row==Q_NUM){ //注意row是從0開(kāi)始到Q_NUM-1結(jié)束。這樣當(dāng)row==Q_NUM時(shí)，已經(jīng)排完所有情況 
        ++RESULT;   //這樣當(dāng)row==Q_NUM時(shí)，已經(jīng)排完所有情況，進(jìn)行輸出就可以了。 
        print();        return ;
    } 
    for(int i=0;i<Q_NUM;++i){ //i代表列數(shù) 
        if(IfQueen(row,i)) //如果row行i列可以放得話，判斷下一行 
            Queen(row+1);
        queens[row][i] = 0; //重置為0，防止下次結(jié)果干擾 
    }
}int main(){
    Queen(0);    cout<<"一共"<<RESULT<<"種擺法\n";    return 0;
}

更多：

毫無(wú)疑問(wèn)，遞歸以及分治思想還有很多用法：斐波那契數(shù)列、快速排序、文件查找、字典樹(shù)的建立等等。理論上遞歸可以解決任何問(wèn)題，而作為我們只需要提供思路，其他的交給計(jì)算機(jī)解決。所以聽(tīng)人說(shuō)過(guò)計(jì)算機(jī)最適合解決遞歸問(wèn)題。但是，有利有弊，遞歸同樣會(huì)消耗更多的內(nèi)存。在初步實(shí)現(xiàn)階段，將大問(wèn)題分而治之，分裝成遞歸函數(shù)，還是邏輯代碼化的最佳表達(dá)。

歡迎進(jìn)一步交流本博文相關(guān)內(nèi)容：

博客園地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信進(jìn)行交流 : xiaochiyijiu@163.com 

歡迎轉(zhuǎn)載 , 但請(qǐng)指明出處  :  )

http://www.cnblogs.com/AsuraDong/p/7045141.html