CH6遞歸.ppt

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