【正文】 漢諾塔問題的描述是：設有 3根標號為 A，B， C的柱子，在 A柱上放著 n個盤子，每一個都比下面的略小一點，要求把 A柱上的盤子全部移到 C柱上，移動的規(guī)則是：（ 1）一次只能移動一個盤子；（ 2）移動過程中大盤子不能放在小盤子上面；（ 3）在移動過程中盤子可以放在 A， B，C的任意一個柱子上。 因為棧頂?shù)墓ぷ饔涗洷囟ㄊ钱斍罢谶\行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動記錄。每一層遞歸所需信息構成一個“工作記錄”，其中包括所有的實在參數(shù)、所有的局部變量以及上一層的返回地址。反之，退出第 I 層遞歸返回至第 I1層。 14. } m n() n = sn s smain:n=10 main:sn= sum:n=10 goto: 5 sum:i= sum:s=0 i=11sum:s=55 main:sn=55 main() sum() main函數(shù) 結束 調用函數(shù) a 調用函數(shù) b 函數(shù) b 函數(shù) a 函數(shù)的嵌套調用，后調用先返回的原則，上述函數(shù)信息傳遞過程需要設立一個棧，將程序運行時需要的數(shù)據(jù)安排在一個棧中，每調用一個函數(shù)，為它在棧頂分配一個存儲區(qū)，每當一個函數(shù)退出時，就釋放它的存儲區(qū)，當前運行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂 三、遞歸調用的實現(xiàn)過程 ? 一個遞歸函數(shù)的運行過程類似于多個函數(shù)的嵌套調用，只是調用函數(shù)和被調用函數(shù)是同一個函數(shù)，因此，和每次調用相關的一個概念是遞歸函數(shù)運行的層次。 i++) 12. s += i。 11. for( i=1。 6. cout sn endl。 4. int sn。 ? 函數(shù)嵌套調用時 ， 后調用的函數(shù)先返回 。 } n！ 遞歸程序源程序 2/2 二、函數(shù)調用的實現(xiàn)過程 ? （ 1）函數(shù)調用 ? 當在一個函數(shù)的運行期間調用另一個函數(shù)時，在運行該被調用函數(shù)之前，需先完成三項任務： ? 將 返回地址 、 所有 實參 等信息傳遞給被調用函數(shù)保存； ? 為被調用函數(shù)的 局部變量 分配存儲區(qū)； ? 將 控制轉移 到被調用函數(shù)的入口。 else z=n*facto(n1)。 { long int z。 printf(The result is %ld,facto(x))。 scanf(%d,amp。 long facto( )。 ? 一個合理的遞歸函數(shù)，一定是一個邏輯上類似于這樣的函數(shù)定義： ? void F() ? { ? …… ? if(…… ) //先判斷某個條件是否成立 ? { ? F()。 ? 為了防止遞歸函數(shù)無休止的調用下去，就要 “ 打斷 ” 這個循環(huán)，我們只有一處 “ 要害 ” 可以下手：在調用會引起遞歸的函數(shù)之前，做一個條件分支判斷，如果條件不成立，則不調用該函數(shù)。子問題的求解通過以一定的方式 修改參數(shù) 進行函數(shù)自身調用加以實現(xiàn)，然后將子問題的解組合成原問題的解。遞歸出口定義了遞歸的終止條件，當程序的執(zhí)行使它得到滿足時，遞歸執(zhí)行過程便終止。 ? 遞歸調用： 在調用一個函數(shù)的過程中又出現(xiàn)直接或間接的調用該函數(shù)本身，稱為函數(shù)的遞歸調用。 ? 函數(shù)與函數(shù)之間是平行的，獨立的。} ? }//switch ? }//while ? }//transform 棧與遞歸函數(shù)的實現(xiàn) ? 一、遞歸函數(shù) ? 二、函數(shù)調用的實現(xiàn)過程 ? 三、遞歸調用的實現(xiàn)過程 一、遞歸函數(shù) ? “ 從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山 …… ” 。) Push(S, ch)。} ? if(ch!=39。 preced(c, ch)) ? {Pass(Suffi,c)。} ? defalt:{while(!Gettop(S,c) amp。 Pop(S, c)。(39。 :{Pop(S, c)。 ? case 39。 :Push(S, ch)。 ? else {switch(ch) ? case 39。 ch=*p。 ? 原表達式： a*b+(cd/e)*f ? 后綴表達式： abc*de/f*+ ? Void transform(char suffix[],char exp[]) ? {InitStack(S)。 ? 對后綴式從左向右“掃描”，遇見操作數(shù)則暫時保存，遇見運算符即可進行運算；此時參加運算的兩個操作數(shù)應該是在它之前剛剛碰到的兩個操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。 void LineEdit ( ) { //利用字符棧 s， 從終端接收一行并傳送至調用過程的數(shù)據(jù)區(qū) 。 例如 ， 假設從終端接受了這樣兩行 字符： whliilre(s*s) outchaputchar(*s= + +)； 則實際有效的是下列兩行： while(*s) putchar(*s++ )； 為此 ， 可設這個輸入緩沖區(qū)為 ——個棧結構 ， 每當從終端接受了一 個字符之后先作如下判別：如果它既不是退格符也不是退行符 ， 則 將該字符壓入棧頂；如果是一個退格符 ， 則從棧頂刪去一個字符；如 果它是一個退行符 ， 則將字符棧清為空棧 。允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。由于用戶在終端上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接受一個字符即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當?shù)摹? else return 0。amp。} break。i++。s,amp。 fit( gettop(s, amp。} ? case 右括號： if( !emptystack( s)amp。 i++。amp。exp) ? {int state=1, i=1。 ? 出現(xiàn)右括號，檢測站內是否為空， ? a若空，則出錯 ? b非空，與棧頂元素（左括號）進行比較，若匹配，則出棧，否則出錯 ? 表達式結束時，若?？眨_；否則，錯誤，左括號多了。 三、直到結束的時候，也沒有等到所期待的右括號。例如： ( ] 二、到來的是不速之客。 例如考慮下列括號序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 當計算機接受了第一個括號后，它期待著與其匹配的第八個括號的出現(xiàn)，然而等來的卻是第二個括號，此時第一個括號“ [ ”只能暫時靠邊，而迫切等待與第二個括號相匹配的、第七個括號“ )”的出現(xiàn)。編程時，將精力集中于問題本身。 棧的應用舉例 由于棧結構具有的后進先出的固有特性，致使棧成為程序設計中的有用工具。 由于鏈棧是動態(tài)分配結點的空間，所以操作時無需考慮上溢出問題。 //定義一個棧的棧頂指針變量 top 為棧頂指針，它唯一地確定一個棧。 Typedef ListNode * LinkStack。 //數(shù)據(jù)域； struct node * next。由于棧的操作是線性表操作的特例，則鏈棧的操作易于實現(xiàn)，它是運算受限的單鏈表。S , SElemType amp。e){ //若棧不空 ， 則用 e返回 s的棧頂元素 ， 并返回 OK； //否則返回 ERROR if( = = ) return ERROR； e=*()； return OK； } //GetTop Status Push (SqStack amp。 //一旦 visit()失敗 ， 則操作失敗 //——基本操作的算法描述 (部分 )——— Status InitStack (SqStack amp。S， SElemType amp。e)； //若棧不空 ， 則用 e返回 s的棧頂元素并返回 OK； 否則返回 ERROR Status Push (SqStack amp。S)； //銷毀棧 s， s不再存在 Status ClearStack (SqStack amp。 //ADTStack的表示與實現(xiàn) //棧的順序存儲表示 define STACK_INIT_SIZE 100 define STACKINCREMENT 10； typedef struct { SElemType * base SElemType * top； int stacksize； }SqStack； //——————基本操作的函數(shù)原型說明 —————— Status InitStack (SqStack amp。 typedef struct{ SElemType *base //棧底指針 ,base的值為 NULL， //則表明棧結構不存在 SElemType *top； //棧頂指針 ,top=base可作為?？? //的標記 int stacksize； //棧的當前可使用的最大容量 }SqStack； 圖 對應關系 。 一般來說 ， 在初始化設空棧時不應限定棧的最大容量 。e)