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

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

【例1】數列｛"J的前幾項為1A 11+1 . 1 11+干1+—T-1+—1+1輸入n，編程求an的精確分數解。分析:這個題目較易，發現a=1,其它情況下有a= 。如要求實數解的話，這基n1+an-1本已經可以寫出遞歸函數了。但由于題目要求精確的分數解，還需做一些調整。設即得an。但發現a=q，則由遞歸關系，有a即得an。但發現n-1p n1+a qp+qn-1 1+—一個問題：求出〃時，需要返回兩個整數：分子q與分母p，而通常的函數只能返回一n-1個整數。這個問題一般有兩類解決辦法，一種是讓求值函數返回一個結構體變量，這樣就可以返回兩個變量了(其實還可以不只兩個呢)；另一種是在求值函數的參數表中加入兩個指針變量或引用變量，通過參數給帶回數值。但由于后一種做法會使程序結構不清晰一一返回值是由參數表得到的，因此我們使用前一種方法。另外，在通過a=q得出a=—L后，a就已經是最簡分數了，無須化簡。證n-1pnp+qn明如下：若q是最簡分數，即說明p,q的最大公約數為1，即對任何1<r<q，都有qmodr與Ppmodr不全為0，不防記qmodr=a、pmodr=b，則有只要a與b不全為0，且a<r,b<r，就有a與(a+b)modr不全為0。因此對任何的1<r<q，有pmodr與(p+q)modr不全為0。而對于q<r<p的情況而言，記pmodr=a，則有由于0<a<r,0<q<r，因此同樣有pmodr與(p+q)modr不全為0。所以對任意1<r<p，都有pmodr與(p+q)modr不全為0，因此它們的最大公約數為1，即_L是最簡分數。雖然這是個要求a(即q)是最簡分數的結論，但由于數p+q n-1 p列第二項為2，是最簡分數，因此可以證明第三項也是最簡分數，同時也證明對所有的a，求出的工就是最簡分數，無須化簡。n p+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()

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

/**//*遞歸鏈表建立函數*//**/linkcreate_list(int*array,intlen,intpos)linkhead;/*鏈表節點的指標/**//*遞歸鏈表建立函數*//**/linkcreate_list(int*array,intlen,intpos)linkhead;/*鏈表節點的指標*/if(pos==len)/*終止條件 */returnNULL;else/*建立節點記憶體*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->data=array[pos];/*建立節點內容*/head->next=create_list(array,len,pos+1);returnhead;))TOC\o"1-5"\h\z/* *//*主程式：建立鏈表后將內容印出. *//* */voidmain()(intlist[6]={1,2,3,4,5,6);/*數組內容*/linkhead; /*指向鏈表開始*/*/head=create_list(list,6,0);/*建立鏈表

*/if(!head)printf(〃記憶體配置失敗!\n〃);exit(1);}printf(〃鏈表的內容:\n〃);print_list(head); /*列印鏈表 */printf(〃\n〃)； /*換行 */卜巡/*遞歸的鏈表建立和反向列印 */#include<>structlist/*鏈表結構宣告 structlist/*鏈表結構宣告 */intdata;/*節點資料intdata;/*節點資料*/TOC\o"1-5"\h\zstructlist*next;/*指向下一節點 */)；typedefstructlistnode;/*定義新型態 */typedefnode*link; /*定義新型態指標*//* *//*遞歸鏈表反向列印函數 *//* */voidprint_list(linkptr)(if(ptr!=NULL) /*終止條件 */(/*遞歸鏈表列印函數調用*/print_list(ptr->next);TOC\o"1-5"\h\zprintf("[%d]”,ptr->data);/*列印節點資料 */))/* *//*遞歸鏈表建立函數 *//* */linkcreate_list(int*array,intlen,intpos)(linkhead; /*鏈表節點的指標*/if(pos==len) /*終止條件 */returnNULL;else/*建立節點記憶體*/head=(link)malloc(sizeof(node));if(!head)returnNULL;head->data=array[pos];/*建立節點內容*/head->next=create_list(array,len,pos+1);returnhead;TOC\o"1-5"\h\z/* *//*主程式：建立鏈表后將內容印出. *//* */voidmain()(1,2,3,4,5,6};/*數組內容*/linkhead; /*指向鏈表開始 */*/head=create_list(list,6,0);/*建立鏈表*/if(!head)(printf(〃記憶體配置失敗！\n〃)；exit(1);)printf(〃鏈表的內容:\n〃)；print_list(head);/*列印鏈表*/printf(〃\n〃)； /*換行 */2/*========================================*//*河諾塔問題 *//**//*/**//*TOC\o"1-5"\h\z/*河內塔問題的遞歸函數 *//* */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);/*第三步驟*/

/*主程式：找出河內塔問題的解.voidmain()hanoi(3,1,2,3);hanoi(3,1,2,3);/*調用遞歸函數*//*應用遞歸來走迷宮/*數字0:表示是可走的路/*應用遞歸來走迷宮/*數字0:表示是可走的路/*數字1：表示是墻壁，不可走的路/*數字2:標示是走過的路/*數字2:標示是走過的路*//*========================================*/intmaze[7][10]={ /*迷宮的數組*/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);/* *//*走迷宮的遞歸函數 *//* */intfind_path(intx,inty)if(x==1&&y==1)(maze[x][y]=2;return1;)elseif(maze[x][y]==0)(maze[x][y]=2;if((find_path(x-/*是否是迷宮出口 *//*記錄最后走過的路 *//*是不是可以走 *//*記錄己經走過的路 */1,y)+/*調用遞歸函數往上*/find_path(x+1,y)+/*往下 */find_path(x,y-1)+/*往左 */find_path(x,y+1))>0)/*往右*/return1;elsemaze[x][y]=0; /*此路不通取消記號 */return0;elsereturn0;/**//*主程式：用遞歸的方法在數組迷宮找出口.*//**//*voidmain()

inti,j;TOC\o"1-5"\h\zfind_path(5,8); /*調用遞歸函數 */printf(〃迷宮的路徑如下圖所示:\n〃)；for(i=1;i<6;i++) /*印出迷宮的圖形 */(for(j=1;j<9;j++)printf(〃％d〃,maze[i][j]);/*印出各座標*/printf(〃\n〃)； /*換行 */)遇/*========================================*//*應用遞歸來解N皇后問題 *//*數字1：表示是放置皇后 *//*數字0:表示沒有放置*//*數字0:表示沒有放置*//**//*#defineMAXQUEEN8 /*最大放置的皇后數*/*/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個皇后的遞歸函數*//**//*intput_queen(intx,inty,inttimes)(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++)(/*遞歸調用放置下一個皇后*/result+=put_queen(i,j,times+1);if(result>0)break;)if(result>0) /*找到了解*/return1;else(pad[x][y]=0; /*清除皇后*/return0;))elsereturn0;/* *//*檢查皇后是否有相互攻擊 *//* -*/(End)馮文科一、遞歸的基本概念。一個函數、概念或數學結構，如果在其定義或說明內部直接或間接地出現對其本身的引用，或者是為了描述問題的某一狀態，必須要用至它的上一狀態，而描述上一狀態，又必須用到它的上一狀態……這種用自己來定義自己的方法，稱之為遞歸或遞歸定義。在程序設計中，函數直接或間接調用自己，就被稱為遞歸調用。二、遞歸的最簡單應用：通過各項關系及初值求數列的某一項。在數學中，有這樣一種數列，很難求出它的通項公式，但數列中各項間關系卻很簡單，于是人們想出另一種辦法來描述這種數列：通過初值及匕與前面臨近幾項之間的關系。要使用這樣的描述方式，至少要提供兩個信息：一是最前面幾項的數值，一是數列間各項的關系。比如階乘數列1、2、6、24、120、720……如果用上面的方式來描述它，應該是：如果需要寫一個函數來求匕的值，那么可以很容易地寫成這樣：intf(intn)if(n==1)return1;returnn*f(n-1);這就是遞歸函數的最簡單形式，從中可以明顯看出遞歸函數都有的一個特點：先處理一些特殊情況一一這也是遞歸函數的第一個出口，再處理遞歸關系一一這形成遞歸函數的第二個出口。遞歸函數的執行過程總是先通過遞歸關系不斷地縮小問題的規模，直到簡單到可以作為特殊情況處理而得出直接的結果，再通過遞歸關系逐層返回到原來的數據規模，最終得出問題的解。以上面求階乘數列的函數f(n)為例。如在求f(3)時，由于3不是特殊值，因此需要計算3*f(2)，但f⑵是對它自己的調用，于是再計算f(2)，2也不是特殊值，需要計算2*f(1)，需要知道f(1)的值，再計算f(1)，1是特殊值，于是直接得出f(1)=1，返回上一步，得f(2)=2*f(1)=2，再返回上一步，得f(3)=3*f(2)=3*2=6，從而得最終解。用圖解來說明，就是

【例1】數列｛"J的前幾項為1A 11+1 . 1 11+干1+—T-1+—1+1輸入n，編程求an的精確分數解。分析:這個題目較易，發現a=1,其它情況下有a= 。如要求實數解的話，這基n1+an-1本已經可以寫出遞歸函數了。但由于題目要求精確的分數解，還需做一些調整。設即得an。但發現a=q，則由遞歸關系，有a即得an。但發現n-1p n1+a qp+qn-1 1+—一個問題：求出〃時，需要返回兩個整數：分子q與分母p，而通常的函數只能返回一n-1個整數。這個問題一般有兩類解決辦法，一種是讓求值函數返回一個結構體變量，這樣就可以返回兩個變量了(其實還可以不只兩個呢)；另一種是在求值函數的參數表中加入兩個指針變量或引用變量，通過參數給帶回數值。但由于后一種做法會使程序結構不清晰一一返回值是由參數表得到的，因此我們使用前一種方法。另外，在通過a=q得出a=—L后，a就已經是最簡分數了，無須化簡。證n-1pnp+qn明如下：若q是最簡分數，即說明p,q的最大公約數為1，即對任何1<r<q，都有qmodr與Ppmodr不全為0，不防記qmodr=a、pmodr=b，則有只要a與b不全為0，且a<r,b<r，就有a與(a+b)modr不全為0。因此對任何的1<r<q，有pmodr與(p+q)modr不全為0。而對于q<r<p的情況而言，記pmodr=a，則有由于0<a<r,0<q<r，因此同樣有pmodr與(p+q)modr不全為0。所以對任意1<r<p，都有pmodr與(p+q)modr不全為0，因此它們的最大公約數為1，即_L是最簡分數。雖然這是個要求a(即q)是最簡分數的結論，但由于數p+q n-1 p列第二項為2，是最簡分數，因此可以證明第三項也是最簡分數，同時也證明對所有的a，求出的工就是最簡分數，無須化簡。n p+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()

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