七、遞歸

　　遞歸算法通常具有這樣的特征：為求解規(guī)模為N的問題，設(shè)法將它分解成一些規(guī)模較小的問題，然后從這些較小問題的解能方便地構(gòu)造出題目所需的解。而這些規(guī)模較小的問題也采用同樣的方法分解成規(guī)模更小的問題，通過規(guī)模更小的問題構(gòu)造出規(guī)模校小的問題的解，如此不斷的反復(fù)分解和綜合，總能分解到最簡單的能直接得到解的情況。

　　因此,在解遞歸算法的題目時,要注意以下幾點:

　　1) 找到遞歸調(diào)用的結(jié)束條件或繼續(xù)遞歸調(diào)用條件.

　　2) 想方設(shè)法將處理對象的規(guī)模縮小或元素減少.

　　3) 由于遞歸調(diào)用可理解為并列同名函數(shù)的多次調(diào)用,而函數(shù)調(diào)用的原則是一層一層調(diào)用,一層一層返回.因此,還要注意理解調(diào)用返回后的下一個語句的作用.在一些簡單的遞歸算法中,往往不需要考慮遞調(diào)用返回后的語句處理.而在一些復(fù)雜的遞歸算法中,則需要考慮遞歸調(diào)用返回后的語句處理和進一步的遞歸調(diào)用.

　　4) 在讀遞歸程序或編寫遞歸程序時,必須要牢記遞歸函數(shù)的作用,這樣便于理解整個函數(shù)的功能和知道哪兒需要寫上遞歸調(diào)用語句.當然,在解遞歸算法的題目時,也需要分清遞歸函數(shù)中的內(nèi)部變量和外部變量.

　　表現(xiàn)形式:

　　●定義是遞歸的(二叉樹,二叉排序樹)
　　●存儲結(jié)構(gòu)是遞歸的(二叉樹,鏈表,數(shù)組)
　　●由前兩種形式得出的算法是遞歸的
　　一般流程: function(variable list(規(guī)模為N))
　　　{ if(規(guī)模小,解已知) return 解;
　　　　else {
　　　　　把問題分成若干個部分;
　　　　　某些部分可直接得到解;
　　　　　而另一部分(規(guī)模為N-1)的解遞歸得到;
　　　　}
　　}
　　例1：求一個鏈表里的最大元素.
　　大家有沒想過這個問題用遞歸來做呢?
　　非遞歸方法大家應(yīng)該都會哦?
　　　　Max(nodetype *h) {
　　　　　nodetype *p;
　　　　　nodetype *q; //存放含最大值的結(jié)點
　　　　　Int max=0;
　　　　　P=h;
　　　　　While(p!=NULL){
　　　　　　if (max<p->data) {
　　　　　　　max=p->data;
　　　　　　　q=p;
　　　　　　}
　　　　　　p=p->next;
　　　　　}
　　　　　return q;
　　　　}
　　下面真經(jīng)來了,嘻嘻嘻~~~
　　　　*max(nodetype *h) {
　　　　　nodetype *temp;
　　　　　temp=max(h->next);
　　　　　if(h->data>temp->data)
　　　　　　return h;
　　　　　else
　　　　　　return temp;
　　　　}
　　大家有空想想下面這個算法：求鏈表所有數(shù)據(jù)的平均值(我也沒試過)，不許偷懶，用遞歸試試哦!
　　遞歸程序員考試題目類型：1)就是鏈表的某些操作(比如上面的求平均值)
　　　　　　　　　　　　　　2)二叉樹(遍歷等)

　　例2.判斷數(shù)組元素是否遞增
　　　　　int jidge(int a[],int n) {
　　　　　　if(n==1) return 1;
　　　　　　else
　　　　　　　if(a[0]>a[1]) return 0;
　　　　　　　else return jidge(a+1,n-1);
　　　　　}

　　例3.求二叉樹的高度(根據(jù)二叉樹的遞歸性質(zhì):(左子樹)根(右子樹))
　　　　　int depth(nodetype *root) {
　　　　　　if(root==NULL) 
　　　　　　　return 0;
　　　　　　else {
　　　　　　　h1=depth(root->lch);
　　　　　　　h2=depth(root->rch);
　　　　　　　return max(h1,h2)+1;
　　　　　　}
　　　　　 }
　　自己想想求二叉樹結(jié)點個數(shù)(與上例類似)

　　例4.已知中序遍歷和后序遍歷,求二叉樹.
　　　設(shè)一二叉樹的:
　　　中序 S:E D F B A G J H C I
　　　　　　^start1 ^j ^end1
　　　后序 T:E F D B J H G I C A
　　　　　　^start2 ^end2
　　　　node *create(char *s,char *t, int start1,int start2,int end1,int end2) 
　　　　{ if (start1>end1) return NULL; //回歸條件
　　　　　root=(node *)malloc(sizeof(node));
　　　　　root->data=t[end2];
　　　　　找到S中T[end2]的位置為 j
　　　　　root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1);
　　　　　root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1);
　　　　　return root;
　　　　}

　　例5.組合問題
　　　n 個數(shù): (1,2,3,4,…n)求從中取r個數(shù)的所有組合.
　　　設(shè)n=5,r=3;
　　　遞歸思想：先固定一位 5 (從另四個數(shù)當中選二個)
　　　　　　　　　　　　　 5,4 (從另三個數(shù)當中選一個)
　　　　　　　　　　　　　 5,4,3 (從另二個數(shù)當中選零個)
　　　即：n-2個數(shù)中取r-2個數(shù)的所有組合
　　　　　…
　　程序:
　　　void combire(int n,int r) {
　　　　for(k=n;k>=n+r-1;k--) {
　　　　　a[r]=k;
　　　　　if(r==0) 打印a數(shù)組(表示找到一個解);
　　　　　else combire(n-1,r-1);
　　　　}
　　　} 

上一頁  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁