遞歸算法詳解完整版

遞歸算法詳解標）隹化管理處編碼[BBX968T-XBB8968-NNJ668-MM9N]

馮文科一、遞歸的基本概念。一個函數(shù)、概念或數(shù)學結(jié)構(gòu)，如果在其定義或說明內(nèi)部直接或間接地出現(xiàn)對其本身的引用，或者是為了描述問題的某一狀態(tài)，必須要用至它的上一狀態(tài)，而描述上一狀態(tài)，又必須用到它的上一狀態(tài)……這種用自己來定義自己的方法，稱之為遞歸或遞歸定義。在程序設計中，函數(shù)直接或間接調(diào)用自己，就被稱為遞歸調(diào)用。二、遞歸的最簡單應用：通過各項關系及初值求數(shù)列的某一項。在數(shù)學中，有這樣一種數(shù)列，很難求出它的通項公式，但數(shù)列中各項間關系卻很簡單，于是人們想出另一種辦法來描述這種數(shù)列：通過初值及氣與前面臨近幾項之間的關系。要使用這樣的描述方式，至少要提供兩個信息：一是最前面幾項的數(shù)值，一是數(shù)列間各項的關系。比如階乘數(shù)列1、2、6、24、120、720……如果用上面的方式來描述它，應該是：如果需要寫一個函數(shù)來求氣的值，那么可以很容易地寫成這樣：:心”“if(n==1)return1;returnn*f(n-1);這就是遞歸函數(shù)的最簡單形式，從中可以明顯看出遞歸函數(shù)都有的一個特點：先處理一些特殊情況一一這也是遞歸函數(shù)的第一個出口，再處理遞歸關系一一這形成遞歸函數(shù)的第二個出口。遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關系不斷地縮小問題的規(guī)模，直到簡單到可以作為特殊情況處理而得出直接的結(jié)果，再通過遞歸關系逐層返回到原來的數(shù)據(jù)規(guī)模，最終得出問題的解。以上面求階乘數(shù)列的函數(shù)f(n)為例。如在求f⑶時，由于3不是特殊值，因此需要計算3*f(2)，但f(2)是對它自己的調(diào)用，于是再計算f(2)，2也不是特殊值，需要計算2*f⑴，需要知道f⑴的值，再計算f⑴，1是特殊值，于是直接得出f⑴=1，返回上一步，得f(2)=2*f⑴=2，再返回上一步，得f⑶=3*f⑵=3*2=6，從而得最終解。用圖解來說明，就是

【例1】數(shù)列｛匕｝的前幾項為1、古^1r、1?—1+商1+r1+—1+1輸入n，編程求an的精確分數(shù)解。分析：這個題目較易，發(fā)現(xiàn)a=1，其它情況下有a=—^。如要求實數(shù)解的話，這基1n1+an-1本已經(jīng)可以寫出遞歸函數(shù)了。但由于題目要求精確的分數(shù)解，還需做一些調(diào)整。設a=區(qū)，則由遞歸關系，有a=——-——=一-一=一P一，再約分化簡，即得a。但發(fā)現(xiàn)n-1pn1+a1+qp+qn一個問題：求出。時，需要返回兩個整數(shù)：分子q與分母p，而通常的函數(shù)只能返回一n-1個整數(shù)。這個問題一般有兩類解決辦法，一種是讓求值函數(shù)返回一個結(jié)構(gòu)體變量，這樣就可以返回兩個變量了(其實還可以不只兩個呢)；另一種是在求值函數(shù)的參數(shù)表中加入兩個指針變量或引用變量，通過參數(shù)給帶回數(shù)值。但由于后一種做法會使程序結(jié)構(gòu)不清晰一一返回值是由參數(shù)表得到的，因此我們使用前一種方法。另外，在通過a=q得出a=—'后，a就已經(jīng)是最簡分數(shù)了，無須化簡。證n-1pnp+qn明如下：若q是最簡分數(shù)，即說明p,q的最大公約數(shù)為1，即對任何1VrVq，都有qmodr與Ppmodr不全為0，不防記qmodr=a、pmodr=b，則有只要a與b不全為0，且aVr,bVr，就有a與(a+b)modr不全為0。因此對任何的1Vr<q，有pmodr與(p+q)modr不全為0。而對于qVr<p的情況而言，記pmodr=a，則有由于0<aVr,0VqVr，因此同樣有pmodr與(p+q)modr不全為0。所以對任意1Vr<p，都有pmodr與(p+q)modr不全為0，因此它們的最大公約數(shù)為1，即_L是最簡分數(shù)。雖然這是個要求a(即q)是最簡分數(shù)的結(jié)論，但由于數(shù)p+qn-1p列第二項為2，是最簡分數(shù)，因此可以證明第三項也是最簡分數(shù)，同時也證明對所有的a，求出的―、就是最簡分數(shù)，無須化簡。np+q具體代碼如下：N(0<N<9)0-Nii+1i+2NNNiNi2i+12(i+1),MAX*sizeof(char));t[n]='\0';for(i=0;i<n;i++)(t[q[i]]='Q';cout<<t<<endl;t[q[i]]='.';}cout<<endl;booltest(inti,intk)(intj；j=0;while(j<k&&abs(j-k)!二abs(q[j]-i))j++；if(j==k&&mark[i]==false)returntrue;elsereturnfalse;}voidsearch(intk)(if(k==n)write();c++;return;}inti;for(i=0;i<n;i++)if(test(i,k))(mark[i]=true;q[k]=i;search(k+1);mark[i]=false;}}intmain()

六、練習【練習】為給定的表達式建立表達式樹，并求值。給定的表達式中，所有數(shù)字都是1位正整數(shù)，出現(xiàn)的符號可能為+、一、*、/、（、）。分析：這是一個與一般數(shù)據(jù)結(jié)構(gòu)書上講的用棧計算的方法本質(zhì)不同的方法。在詳細說明這個算法之前，需要首先明確這個算法用到的概念1、單元：一個單元可能是用括號括起來的一個表達式，或是一個整數(shù)；2、項：一個項是指由*與/連接起來的若干單元；3、表達式：一個表達式是指由+或一連接起來的若干項。要建立表達式樹，需要三個函數(shù)互相調(diào)用的函數(shù)：一個是getunit，用于建立一個單元；一個是getexpr，用于建立一個項，另一個就是build，用于建立一個表達式。getunit函數(shù)較易，如果字符串首字母是（的話，那么從它后面的字符開始用build建立一個表達式，這個表達式就是一個單元；否則，就處理一個整數(shù)；getexpr函數(shù)是建立在getunit之上的，它先用getunit建立一個單元，然后不停地考察之后地連接符號是不是*或/，若是，則不停地重復讀連接符、建立另一個單元、建立連接的操作，直到連接符號不是*或/為止。build函數(shù)是用于最終建立表達式的，它先用getexpr建立一個項，再用符號將剩余的各項連接成二叉樹。代碼如下：if(n>0)(hanoi(n-1,x,z,y);hanoi(n-1,y,x,z);}.w[10]中intknap(ints,intn)(算法32是求n個數(shù)的和的遞歸算法。算法33是相應的迭代版本。假設n個數(shù)已存儲在數(shù)組a的分量a[1]，…,a[n]中。floatsum(intn){.a[n]都置為0a[0]=1;*//**/voidmain()(inti;for(i=0;i<5;i++)printf("%d!=%d\n”,i,factorial(i));/*遞歸階乘函數(shù)調(diào)用*/}/*========================================*/TOC\o"1-5"\h\z/*使用列印數(shù)組函數(shù)來說明遞歸調(diào)用*//*========================================*/intlist[6]=(1,2,3,4,5,6};/*數(shù)組內(nèi)容*//**//*遞歸數(shù)組反向列印函數(shù)*//**/voidinvert_array(intj)(if(j<6)/*終止條件*//*遞歸鏈表列印函數(shù)調(diào)用*/invert_array(j+1);printf("[%d]”,list[j]);/*列印元素資料*/}TOC\o"1-5"\h\z/**//*主程式：反向列印數(shù)組內(nèi)容.*//**/voidmain()(inti;printf（"數(shù)組的內(nèi)容：\n〃）;for(i=0;i<6;i++)printf(z/[%d]/z,list[i]):/*列印元素資料*/printf(〃\n〃)；/*換行*/printf(〃遞歸列印數(shù)組的內(nèi)容:\n〃)；invert_array(0);/*調(diào)用列印函數(shù)*/printf(〃\n〃)；/*換行*/遞歸階乘函數(shù)來說明遞歸內(nèi)部處理*/遞歸階乘函數(shù)intfactrial(intj)intsum=0;/*階乘總和變數(shù)*/inttemp=0;/*階乘總和暫存變數(shù)*/if(j==0)/*終止條件*/sum=1;printf(”到達終止條件(j=0)\n");}else(printf("從函數(shù)factrial(%d)調(diào)用前的狀態(tài)：sum=%d\n",j,sum);temp=factrial(j-1);/*遞歸階乘函數(shù)調(diào)用*/j,sum);sum=j*temp;/*計算j!的值*/printf("==＞在計算%d!階乘后的狀態(tài)：sum=%d\n”,j,sum);}returnsum;}/**//*主程式：計算整數(shù)4的階乘.*//**/voidmain()printf("4!=%d\n",factrial(4));/*遞歸階乘函數(shù)調(diào)用*//*========================================*/TOC\o"1-5"\h\z/*遞歸的鏈表建立和列印*//*========================================*/#include<>structlist/*鏈表結(jié)構(gòu)宣告*/(intdata;/*節(jié)點資料*/structlist*next;/*指向下一節(jié)點*/};typedefnode*link;/*定義新型態(tài)指標*/TOC\o"1-5"\h\z/**//*遞歸鏈表列印函數(shù)*//**/voidprint_list(linkptr)(if(ptr!=NULL)/*終止條件*/(printf("[%d]",ptr->data);/*列印節(jié)點資料*//*遞歸鏈表列印函數(shù)調(diào)用*/print_list(ptr->next);}/*遞歸鏈表建立函數(shù)*//**/linkcreate_list(int*array,intlen,intpos)(linkhead;/*鏈表節(jié)點的指標*/if(pos==len)/*終止條件*/returnNULL;else(/*建立節(jié)點記憶體*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->next=create_list(array,len,pos+1);returnhead;}}TOC\o"1-5"\h\z/**//*主程式：建立鏈表后將內(nèi)容印出.*//**/voidmain()(intlist[6]=(1,2,3,4,5,6};/*數(shù)組內(nèi)容*/linkhead;/*指向鏈表開始*/*/head=create_list(list,6,0);/*建立鏈表*/if(!head)printf(〃記憶體配置失敗!\n〃);exit(1);}printf(〃鏈表的內(nèi)容:\n〃);print_list(head);/*列印鏈表*/printf(〃\n〃)；/*換行*/}窺/*遞歸的鏈表建立和反向列印*/#include<>structlist/*鏈表結(jié)構(gòu)宣告*/

structlist/*鏈表結(jié)構(gòu)宣告*/intdata;/*節(jié)點資料*/TOC\o"1-5"\h\zstructlist*next;/*指向下一節(jié)點*/｝；typedefstructlistnode;/*定義新型態(tài)*/typedefnode*link;/*定義新型態(tài)指標*//**//*遞歸鏈表反向列印函數(shù)*//**/voidprint_list(linkptr)(if(ptr!=NULL)/*終止條件*/(/*遞歸鏈表列印函數(shù)調(diào)用*/print_list(ptr->next);}}TOC\o"1-5"\h\z/**//*遞歸鏈表建立函數(shù)*//**/linkcreate_list(int*array,intlen,intpos)(linkhead;/*鏈表節(jié)點的指標*/if(pos==len)/*終止條件*/returnNULL;else/*建立節(jié)點記憶體*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->data=array[pos];/*建立節(jié)點內(nèi)容*/head->next=create_list(array,len,pos+1);returnhead;TOC\o"1-5"\h\z/**//*主程式：建立鏈表后將內(nèi)容印出.*//**/voidmain()linkhead;/*指向鏈表開始*/head=create_list(list,6,0);/*建立鏈表*/if(!head)(printf("記憶體配置失??！\n〃)；exit(1);}printf("鏈表的內(nèi)容：\n〃)；print_list(head);/*列印鏈表*/printf(〃\n〃)；/*換行*/”；：％/*========================================*//*河諾塔問題*//**//*TOC\o"1-5"\h\z/*河內(nèi)塔問題的遞歸函數(shù)*//**/inthanoi(intdishs,intpeg1,intpeg2,intpeg3)(if(dishs==1)/*終止條件*/printf("盤子從%d移到％d\n”,peg1,peg3);else(hanoi(dishs-1,peg1,peg3,peg2);/*第一步驟*/printf("盤子從%d移到％d\n”,peg1,peg3);hanoi(dishs-1,peg2,peg1,peg3);/*第三步驟*/

/*主程式：找出河內(nèi)塔問題的解.voidmain()hanoi(3,1,2,3);hanoi(3,1,2,3);/*調(diào)用遞歸函數(shù)*//*應用遞歸來走迷宮/*數(shù)字0:表示是可走的路/*數(shù)字1：表示是墻壁，不可走的路/*數(shù)字2:標示是走過的路*//*========================================*/intmaze[7][10]={/*迷宮的數(shù)組/*數(shù)字2:標示是走過的路*/TOC\o"1-5"\h\z1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1);/**//*走迷宮的遞歸函數(shù)*//**/intfind_path(intx,inty)(maze[x][y]=2;return1;}elseif(maze[x][y]==0)(maze[x][y]=2;if((find_path(x-/*記錄最后走過的路*//*是不是可以走*//*記錄己經(jīng)走過的路*/1,y)+/*調(diào)用遞歸函數(shù)往上*/find_path(x+1,y)+/*往下*/find_path(x,y-1)+/*往左*/find_path(x,y+1))>0)/*往右*/return1;else(maze[x][y]=0;/*此路不通取消記號*/return0;}}elsereturn0;}/**//*主程式：用遞歸的方法在數(shù)組迷宮找出口.*//**/voidmain()inti,j;find_path(5,8);/*調(diào)用遞歸函數(shù)*/printf(-迷宮的路徑如下圖所示:\n〃)；for(i=1;i<6;i++)/*印出迷宮的圖形*/(for(j=1;j<9;j++)printf(〃％d〃，maze[i][j]);/*印出各座標*/TOC\o"1-5"\h\zprintf(〃\n〃)；/*換行*/}}，/*========================================*//*應用遞歸來解N皇后問題*//*數(shù)字1：表示是放置皇后*/#defineMAXQUEEN8/*最大放置的皇后數(shù)*/intpad[MAXQUEEN][MAXQUEEN]=(/*NXN的棋盤*/TOC\o"1-5"\h\z0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);/**//*放N個皇后的遞歸函數(shù)*/intput_queen(intx,inty,int/*放N個皇后的遞歸函數(shù)*/inti,j,result=0;if(times>MAXQUEEN)/*終止條件*/return1;elseif(place(x,y))/*檢查是否可放置皇后*/(pad[x][y]=1;/*放置皇后*/for(i=0;i<MAXQUEEN;i++)for(j=0;j<MAXQUEEN;j++)(/*遞歸調(diào)用放置下一個皇后*/result+=put_queen(i,j,times+1);if(result>0)break;}if(result>0)/*找到了解*/return1;else(pad[x][y]=0;/*清除皇后*/return0;}}elsereturn0;*//*/*檢查皇后是否有相互攻擊*//*-*/(End)馮文科一、遞歸的基本概念。一個函數(shù)、概念或數(shù)學結(jié)構(gòu)，如果在其定義或說明內(nèi)部直接或間接地出現(xiàn)對其本身的引用，或者是為了描述問題的某一狀態(tài)，必須要用至它的上一狀態(tài)，而描述上一狀態(tài)，又必須用到它的上一狀態(tài)……這種用自己來定義自己的方法，稱之為遞歸或遞歸定義。在程序設計中，函數(shù)直接或間接調(diào)用自己，就被稱為遞歸調(diào)用。二、遞歸的最簡單應用：通過各項關系及初值求數(shù)列的某一項。在數(shù)學中，有這樣一種數(shù)列，很難求出它的通項公式，但數(shù)列中各項間關系卻很簡單，于是人們想出另一種辦法來描述這種數(shù)列：通過初值及氣與前面臨近幾項之間的關系。要使用這樣的描述方式，至少要提供兩個信息：一是最前面幾項的數(shù)值，一是數(shù)列間各項的關系。比如階乘數(shù)列1、2、6、24、120、720……如果用上面的方式來描述它，應該是：如果需要寫一個函數(shù)來求氣的值，那么可以很容易地寫成這樣：:心”“if(n==1)return1;returnn*f(n-1);這就是遞歸函數(shù)的最簡單形式，從中可以明顯看出遞歸函數(shù)都有的一個特點：先處理一些特殊情況一一這也是遞歸函數(shù)的第一個出口，再處理遞歸關系一一這形成遞歸函數(shù)的第二個出口。遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關系不斷地縮小問題的規(guī)模，直到簡單到可以作為特殊情況處理而得出直接的結(jié)果，再通過遞歸關系逐層返回到原來的數(shù)據(jù)規(guī)模，最終得出問題的解。以上面求階乘數(shù)列的函數(shù)f(n)為例。如在求f⑶時，由于3不是特殊值，因此需要計算3*f(2)，但f(2)是對它自己的調(diào)用，于是再計算f(2)，2也不是特殊值，需要計算2*f⑴，需要知道f⑴的值，再計算f⑴，1是特殊值，于是直接得出f⑴=1，返回上一步，得f(2)=2*f⑴=2，再返回上一步，得f⑶=3*f⑵=3*2=6，從而得最終解。用圖解來說明，就是

【例1】數(shù)列｛匕｝的前幾項為1、古^1r、1?—1+商1+r1+—1+1輸入n，編程求an的精確分數(shù)解。分析：這個題目較易，發(fā)現(xiàn)a=1，其它情況下有a=—^。如要求實數(shù)解的話，這基1n1+an-1本已經(jīng)可以寫出遞歸函數(shù)了。但由于題目要求精確的分數(shù)解，還需做一些調(diào)整。設a=區(qū)，則由遞歸關系，有a=——-——=一-一=一P一，再約分化簡，即得a。但發(fā)現(xiàn)n-1pn1+a1+qp+qn一個問題：求出。時，需要返回兩個整數(shù)：分子q與分母p，而通常的函數(shù)只能返回一n-1個整數(shù)。這個問題一般有兩類解決辦法，一種是讓求值函數(shù)返回一個結(jié)構(gòu)體變量，這樣就可以返回兩個變量了(其實還可以不只兩個呢)；另一種是在求值函數(shù)的參數(shù)表中加入兩個指針變量或引用變量，通過參數(shù)給帶回數(shù)值。但由于后一種做法會使程序結(jié)構(gòu)不清晰一一返回值是由參數(shù)表得到的，因此我們使用前一種方法。另外，在通過a=q得出a=—'后，a就已經(jīng)是最簡分數(shù)了，無須化簡。證n-1pnp+qn明如下：若q是最簡分數(shù)，即說明p,q的最大公約數(shù)為1，即對任何1VrVq，都有qmodr與Ppmodr不全為0，不防記qmodr=a、pmodr=b，則有只要a與b不全為0，且aVr,bVr，就有a與(a+b)modr不全為0。因此對任何的1Vr<q，有pmodr與(p+q)modr不全為0。而對于qVr<p的情況而言，記pmodr=a，則有由于0<aVr,0VqVr，因此同樣有pmodr與(p+q)modr不全為0。所以對任意1Vr<p，都有pmodr與(p+q)modr不全為0，因此它們的最大公約數(shù)為1，即_L是最簡分數(shù)。雖然這是個要求a(即q)是最簡分數(shù)的結(jié)論，但由于數(shù)p+qn-1p列第二項為2，是最簡分數(shù)，因此可以證明第三項也是最簡分數(shù)，同時也證明對所有的a，求出的―、就是最簡分數(shù)，無須化簡。np+q具體代碼如下：N(0<N<9)0-Nii+1i+2NNNiNi2i+12(i+1),MAX*sizeof(char));t[n]='\0';for(i=0;i<n;i++)(t[q[i]]='Q';cout<<t<<endl;t[q[i]]='.';}cout<<endl;booltest(inti,intk)(intj；j=0;while(j<k&&abs(j-k)!二abs(q[j]-i))j++；if(j==k&&mark[i]==false)returntrue;elsereturnfalse;}voidsearch(intk)(if(k==n)write();c++;return;}inti;for(i=0;i<n;i++)if(test(i,k))(mark[i]=true;q[k]=i;search(k+1);mark[i]=false;}}intmain()

六、練習【練習】為給定的表達式建立表達式樹，并求值。給定的表達式中，所有數(shù)字都是1位正整數(shù)，出現(xiàn)的符號可能為+、一、*、/、（、）。分析：這是一個與一般數(shù)據(jù)結(jié)構(gòu)書上講的用棧計算的方法本質(zhì)不同的方法。在詳細說明這個算法之前，需要首先明確這個算法用到的概念1、單元：一個單元可能是用括號括起來的一個表達式，或是一個整數(shù)；2、項：一個項是指由*與/連接起來的若干單元；3、表達式：一個表達式是指由+或一連接起來的若干項。要建立表達式樹，需要三個函數(shù)互相調(diào)用的函數(shù)：一個是getunit，用于建立一個單元；一個是getexpr，用于建立一個項，另一個就是build，用于建立一個表達式。getunit函數(shù)較易，如果字符串首字母是（的話，那么從它后面的字符開始用build建立一個表達式，這個表達式就是一個單元；否則，就處理一個整數(shù)；getexpr函數(shù)是建立在getunit之上的，它先用getunit建立一個單元，然后不停地考察之后地連接符號是不是*或/，若是，則不停地重復讀連接符、建立另一個單元、建立連接的操作，直到連接符號不是*或/為止。build函數(shù)是用于最終建立表達式的，它先用getexpr建立一個項，再用符號將剩余的各項連接成二叉樹。代碼如下：.從這些關系中，我們很容易看出在余數(shù)上加上‘0’就可以產(chǎn)生對應字符的代碼。接著就打印出余數(shù)。下一步再取商的值，4267/10等于426。然后用這個值重復上述步驟。這種處理方法存在的唯一問題是它產(chǎn)生的數(shù)字次序正好相反，它們是逆向打印的。所以在我們的程序中使用遞歸來修正這個問題。我們這個程序中的函數(shù)是遞歸性質(zhì)的，因為它包含了一個對自身的調(diào)用。乍一看，函數(shù)似乎永遠不會終止。當函數(shù)調(diào)用時，它將調(diào)用自身，第2次調(diào)用還將調(diào)用自身，以此類推，似乎永遠調(diào)用下去。這也是我們在剛接觸遞歸時最想不明白的事情。但是，事實上并不會出現(xiàn)這種情況。這個程序的遞歸實現(xiàn)了某種類型的螺旋狀while循環(huán)。while循環(huán)在循環(huán)體每次執(zhí)行時必須取得某種進展，逐步迫近循環(huán)終止條件。遞歸函數(shù)也是如此，它在每次遞歸調(diào)用后必須越來越接近某種限制條件。當遞歸函數(shù)符合這個限制條件時，它便不在調(diào)用自身。在程序中，遞歸函數(shù)的限制條件就是變量quotient為零。在每次遞歸調(diào)用之前，我們都把quotient除以10，所以每遞歸調(diào)用一次，它的值就越來越接近零。當它最終變成零時，遞歸便告終止。/*接受一個整型值(無符號0,把它轉(zhuǎn)換為字符并打印它，前導零被刪除*/#include<>intbinary_to_ascii(unsignedintvalue)ge項quotient;quotient=value/10;if(quotient!=0)binary_to_ascii(quotient);遞歸是如何幫助我們以正確的順序打印這些字符呢下面是這個函數(shù)的工作流程將參數(shù)值除以10如果quotient的值為非零，調(diào)用binary-to-ascii打印quotient當前值的各位數(shù)字接著，打印步驟1中除法運算的余數(shù)注意在第2個步驟中，我們需要打印的是quotient當前值的各位數(shù)字。我們所面臨的問題和最初的問題完全相同，只是變量quotient的值變小了。我們用剛剛編寫的函數(shù)（把整數(shù)轉(zhuǎn)換為各個數(shù)字字符并打印出來）來解決這個問題。由于quotient的值越來越小，所以遞歸最終會終止。一旦你理解了遞歸，閱讀遞歸函數(shù)最容易的方法不是糾纏于它的執(zhí)行過程，而是相信遞歸函數(shù)會順利完成它的任務。如果你的每個步驟正確無誤，你的限制條件設置正確，并且每次調(diào)用之后更接近限制條件，遞歸函數(shù)總是能正確的完成任務。但是，為了理解遞歸的工作原理，你需要追蹤遞歸調(diào)用的執(zhí)行過程，所以讓我們來進行這項工作。追蹤一個遞歸函數(shù)的執(zhí)行過程的關鍵是理解函數(shù)中所聲明的變量是如何存儲的。當函數(shù)被調(diào)用時，它的變量的空間是創(chuàng)建于運行時堆棧上的。以前調(diào)用的函數(shù)的變量扔保留在堆棧上，但他們被新函數(shù)的變量所掩蓋，因此是不能被訪問的。當遞歸函數(shù)調(diào)用自身時，情況于是如此。每進行一次新的調(diào)用，都將創(chuàng)建一批變量，他們將掩蓋遞歸函數(shù)前一次調(diào)用所創(chuàng)建的變量。當我追蹤一個遞歸函數(shù)的執(zhí)行過程時，必須把分數(shù)不同次調(diào)用的變量區(qū)分開來，以避免混淆。程序中的函數(shù)有兩個變量：參數(shù)value和局部變量quotient。下面的一些圖顯示了堆棧的狀態(tài)，當前可以訪問的變量位于棧頂。所有其他調(diào)用的變量飾以灰色的陰影，表示他們不能被當前正在執(zhí)行的函數(shù)訪問。假定我們以4267這個值調(diào)用遞歸函數(shù)。當函數(shù)剛開始執(zhí)行時，堆棧的內(nèi)容如下圖所示：執(zhí)行除法之后，堆棧的內(nèi)容如下：接著，if語句判斷出quotient的值非零，所以對該函數(shù)執(zhí)行遞歸調(diào)用。當這個函數(shù)第二次被調(diào)用之初，堆棧的內(nèi)容如下：堆棧上創(chuàng)建了一批新的變量，隱藏了前面的那批變量，除非當前這次遞歸調(diào)用返回，否則他們是不能被訪問的。再次執(zhí)行除法運算之后，堆棧的內(nèi)容如下：quotient的值現(xiàn)在為42，仍然非零，所以需要繼續(xù)執(zhí)行遞歸調(diào)用，并再創(chuàng)建一批變量。在執(zhí)行完這次調(diào)用的出發(fā)運算之后，堆棧的內(nèi)容如下：此時，quotient的值還是非零，仍然需要執(zhí)行遞歸調(diào)用。在執(zhí)行除法運算之后，堆棧的內(nèi)容如下：不算遞歸調(diào)用語句本身，到目前為止所執(zhí)行的語句只是除法運算以及對quotient的值進行測試。由于遞歸調(diào)用這些語句重復執(zhí)行，所以它的效果類似循環(huán)：當quotient的值非零時，把它的值作為初始值重新開始循環(huán)。但是，遞歸調(diào)用將會保存一些信息（這點與循環(huán)不同），也就好是保存在堆棧中的變量值。這些信息很快就會變得非常重要?，F(xiàn)在quotient的值變成了零，遞歸函數(shù)便不再調(diào)用自身，而是開始打印輸出。然后函數(shù)返回，并開始銷毀堆棧上的變量值。每次調(diào)用putchar得到變量value的最后一個數(shù)字，方法是對value進行模10取余運算，其結(jié)果是一個0到9之間的整數(shù)。把它與字符常量‘0’相加，其結(jié)果便是對應于這個數(shù)字的ASCII字符，然后把這個字符打印出來。輸出4：接著函數(shù)返回，它的變量從堆棧中銷毀。接著，遞歸函數(shù)的前一次調(diào)用重新繼續(xù)執(zhí)行，她所使用的是自己的變量，他們現(xiàn)在位于堆棧的頂部。因為它的value值是42,所以調(diào)用putchar后打印出來的數(shù)字是2。輸出42：接著遞歸函數(shù)的這次調(diào)用也返回，它的變量也被銷毀，此時位于堆棧頂部的是遞歸函數(shù)再前一次調(diào)用的變量。遞歸調(diào)用從這個位置繼續(xù)執(zhí)行，這次打印的數(shù)字是6。在這次調(diào)用返回之前，堆棧的內(nèi)容如下：輸出426：現(xiàn)在我們已經(jīng)展開了整個遞歸過程，并回到該函數(shù)最初的調(diào)用。這次調(diào)用打印出數(shù)字7，也就是它的value參數(shù)除10的余數(shù)。輸出4267：然后，這個遞歸函數(shù)就徹底返回到其他函數(shù)調(diào)用它的地點。如果你把打印出來的字符一個接一個排在一起，出現(xiàn)在打印機或屏幕上，你將看到正確的值：4267漢諾塔問題遞歸算法分析：一個廟里有三個柱子，第一個有64個盤子，從上往下盤子越來越大。要求廟里的老和尚把這64個盤子全部移動到第三個柱子上。移動的時候始終只能小盤子壓著大盤子。而且每次只能移動一個。1、此時老和尚（后面我們叫他第一個和尚）覺得很難，所以他想：要是有一個人能把前63個盤子先移動到第二個柱子上，我再把最后一個盤子直接移動到第三個柱子，再讓那個人把剛才的前63個盤子從第二個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他找了比他年輕的和尚（后面我們叫他第二個和尚），命令：你丫把前63個盤子移動到第二柱子上然后我自己把第64個盤子移動到第三個柱子上后你把前63個盤子移動到第三柱子上2、第二個和尚接了任務，也覺得很難，所以他也和第一個和尚一樣想：要是有一個人能把前62個盤子先移動到第三個柱子上，我再把最后一個盤子直接移動到第二個柱子，再讓那個人把剛才的前62個盤子從第三個柱子上移動到第三個柱子上，我的任務就完成了，簡單。所以他也找了比他年輕的和尚（后面我們叫他第三和尚），命令：你把前62個盤子移動到第三柱子上然后我自己把第63個盤子移動到第二個柱子上后你