CH6遞歸.ppt

第六章遞歸 遞歸的定義遞歸中的參數(shù)傳遞遞歸的實例 一 遞歸的定義 1 定義 簡單地說 就是子程序或函數(shù)重復(fù)調(diào)用自己 并傳入不同的參數(shù)值來執(zhí)行的一種程序設(shè)計方法 2 以下三種情況常常用到遞歸方法 定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的 1 調(diào)用前 1 將所有的實參 返回地址傳遞給被調(diào)用函數(shù)保存 2 為被調(diào)用函數(shù)的局部變量分配存儲區(qū) 3 將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口 調(diào)用后 1 保存被調(diào)用函數(shù)的計算結(jié)果 2 釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū) 3 依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù) 二 函數(shù)調(diào)用的過程 多個函數(shù)嵌套調(diào)用時 按照 后調(diào)用先返回 的原則進行 intmain intm n first m n 1 intfirst ints intt inti second i 2 intsecond intd intx y 3 2 函數(shù)調(diào)用過程 在C語言中 一般采用堆棧這上數(shù)據(jù)結(jié)構(gòu)來記錄函數(shù)調(diào)用后的返回地址 即 當(dāng)主函數(shù)執(zhí)行到first m n 時 堆棧需記錄下一行程序語句的地址 以便在first m n 執(zhí)行完后 能順利返回主程序中繼續(xù)執(zhí)行未執(zhí)行的程序語句 其他類推 intmain intm n inti intx y 3 2 1 3 函數(shù)嵌套調(diào)用過程示例 4函數(shù)的遞歸調(diào)用intf x intx inty z z f y return 2 z f函數(shù)調(diào)用f函數(shù) 例1 階乘函數(shù) 三 遞歸的實例 1 定義是遞歸的 longfact longn longy if n 0 y 1 elsey n fact n 1 returny 求解階乘函數(shù)的遞歸算法 01020304050607 includemain longx k scanf ld 010203040506070809101112131415 一個完整的求階乘的程序 求解階乘n 的過程 主程序main fact 4 參數(shù)4計算4 fact 3 返回24 參數(shù)3計算3 fact 2 返回6 參數(shù)2計算2 fact 1 返回2 參數(shù)1計算1 fact 0 返回1 參數(shù)0直接定值 1返回1 參數(shù)傳遞 結(jié)果返回 遞歸調(diào)用 回歸求值 分析 1 了解題意是否適合用遞歸來解 2 決定遞歸結(jié)束條件 3 決定遞歸執(zhí)行部分 4 例1中每次執(zhí)行的過程相似 唯一的不同點為其中一個傳入?yún)?shù) 每次執(zhí)行都遞減 遞歸結(jié)束條件n為0時返回其階乘的值 否則繼續(xù)調(diào)用程序并遞減傳入?yún)?shù)值 5 處理遞歸問題 常采用if語句來判斷是否符合遞歸結(jié)束條件 其格式如下 if 符合遞歸結(jié)束條件 遞歸結(jié)束的結(jié)果 else遞歸執(zhí)行部分 例2 費氏級數(shù) FibonacciNumbers 問題 程序構(gòu)思 遞歸結(jié)束條件 當(dāng)n1時 返回費氏級數(shù)值為Fib n 1 Fib n 2 includemain intnum result scanf ld 010203040506070809101112131415 2 數(shù)據(jù)結(jié)構(gòu)是遞歸的 一個結(jié)點 它的指針域為NULL 是一個單鏈表 一個結(jié)點 它的指針域指向單鏈表 仍是一個單鏈表 例如 單鏈表結(jié)構(gòu) f f 搜索鏈表最后一個結(jié)點并打印其數(shù)值voidPrint ListNode f if f next NULL printf d n f data elsePrint f next f f f f f a0 a1 a2 a3 a4 遞歸找鏈尾 在鏈表中尋找等于給定值的結(jié)點并打印其數(shù)值voidPrint ListNode f ListData f f f f 遞歸找含x值的結(jié)點 x 例1 漢諾塔 TowerofHanoi 問題 3 問題的解法是遞歸的 有三根木樁分別為A B C 有n個鐵盤由小到大的放置在A木樁上 現(xiàn)需要將A木樁上的n個盤借助B木樁移到C木樁上 且必須遵守 一次只能移動一個盤子 每根木樁必須維持小盤在上 大盤在下的原則 漢諾塔 TowerofHanoi 問題的解法 如果n 1 則將這一個盤子直接從A柱移到C柱上 否則 執(zhí)行以下三步 用C柱做過渡 將A柱上的 n 1 個盤子移到B柱上 將A柱上最后一個盤子直接移到C柱上 用A柱做過渡 將B柱上的 n 1 個盤子移到C柱上 voidHanoi intn charx chary charz if n 1 printf Movedisk dfrom cto c n x z else Hanoi n 1 x z y printf Movedisk dfrom cto c n x z Hanoi n 1 y x z 漢諾塔問題的遞歸算法 0102030405060708091011 includevoidHanoi intn charx chary charz if n 1 printf Movedisk dfrom cto c n x z else Hanoi n 1 x z y printf Movedisk dfrom cto c n x z Hanoi n 1 y x z voidmain intnum charone two three scanf d 0102030405060708091011121314151617181920 遞歸層次 運行語句序號 遞歸工作棧狀態(tài) 返址 盤號 x y z 塔與圓盤的狀態(tài) 1 2 3 2 1 2 4 5 1 2 4 5 1 2 3 9 6 7 漢諾塔問題的遞歸調(diào)用過程 遞歸層次 運行語句序號 遞歸工作棧狀態(tài) 返址 盤號 x y z 塔與圓盤的狀態(tài) 3 2 1 2 1 2 3 9 8 9 6 7 1 2 4 5 遞歸層次 運行語句序號 遞歸工作棧狀態(tài) 返址 盤號 x y z 塔與圓盤的狀態(tài) 3 2 3 2 1 2 3 9 6 7 1 2 3 9 8 9 遞歸層次 運行語句序號 遞歸工作棧狀態(tài) 返址 盤號 x y z 塔與圓盤的狀態(tài) 1 0 8 9 ?？?例2 迷宮問題 a 迷宮的圖形表示 b 迷宮的二維數(shù)組表示 求解迷宮問題的簡單方法是 從入口出發(fā) 沿某一方向進行探索 若能走通 則繼續(xù)向前走 否則沿原路返回 換一方向再進行探索 直到所有可能的通路都探索到為止 為避免走回到已經(jīng)進入的點 包括已在當(dāng)前路徑上的點和曾經(jīng)在當(dāng)前路徑上的點 凡是進入過的點都應(yīng)做上記號 為了記錄當(dāng)前位置以及在該位置上所選的方向 算法中設(shè)置了一個棧 棧中每個元素包括三項 分別記錄當(dāng)前位置的行坐標(biāo) 列坐標(biāo)以及在該位置上所選的方向 即directon數(shù)組的下標(biāo)值 棧用順序存儲結(jié)構(gòu)實現(xiàn) 棧中元素的說明如下 structNodeMaze intx y d typedefstructNodeMazeDataType 算法4 15求迷宮中一條路徑的算法voidmazePath int maze int direction intx1 inty1 intx2 inty2 迷宮maze M N 中求從入口maze x1 y1 到出口maze x2 y2 的一條路徑 其中1 x1 x2 M 2 1 y1 y2 N 2 inti j k kk intg h PSeqStackst DataTypeelement st createEmptyStack seq maze x1 y1 2 從入口開始進入 作標(biāo)記 element x x1 element y y1 element d 1 push seq st element 入口點進棧 while notisEmptyStack seq st 走不通時 一步步回退 element top seq st i element x j element y k element d 1 pop seq st while kt kk printf the dnodeis d d n kk st s kk x st s kk y printf the dnodeis d d n kk i j printf the dnodeis d d n kk 1 g h return if maze g h 0 走到?jīng)]走過的點 maze g h 2 作標(biāo)記 element x i eleme