[工學(xué)]第五講函數(shù)-資料下載頁
2025-10-04 16:19本頁面
【正文】 !”) 。 else printf(”%d ! = %”, i, facto(i) ) 。 } 說明 : 遞歸包括 “ 遞推 ” 和 “ 回歸 ” 需有結(jié)束遞歸過程的條件 例 2 計算 n! = 1 當 n=1 或 n=0時 n(n1)! 當 n1時 4 * facto(3) 3 * facto(2) 2* facto(1) 1 2*1 (3* 2*1) (4* 3* 2*1) 輸出 (4* 3* 2*1) 遞推 回歸 計算 facto(4) 遞歸程序的執(zhí)行過程 facto ( n ) int n。 { int s。 if ( n == 1 ) s = 1。 else s = n * facto(n1)。 return (s)。 } facto ( int n ) { int s。 if ( n == 1 ) s = 1。 else { s = facto (n1)。 s = n*s。 } return (s)。 } 等價于 當 n = 1 時 n! = 1 當 n 1 時 n! = n * (n1)! 遞歸程序的執(zhí)行過程 facto(int n) { int s。 if(n= =1) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } facto(int n) int s。 if(n= =1) facto(int n) { int s。 if(n= =1) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } s=facto(n1) facto(int n) int s。 if(n= =1) facto(int n) { int s。 if(n= =1) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } s=facto(n1) facto(int n) { int s。 if(n= =1) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } facto(int n) facto(int n) int s。 int s。 if(n= =1) if(n= =1) s=facto(n1) s = 1 return(1) s=n*s=2*1 return(2) return(6) s=n*s=3*2 s=n*s=4*6 return(24) 1 2 3 4 3 2 1 N=4 N=3 N=2 N=1 ? 遞歸的基礎(chǔ) 變量存儲類型 （ 自動變量 ） 的特點 ， 保證了在每層遞歸調(diào)用的過程中 ， 變量可以保持相對于各個層次的獨立性 ， 不會發(fā)生相互干擾 。 不準確地說：遞歸過程實際上一個隱含著循環(huán)的過程 。 ? 對遞歸的認識 所有的遞歸問題一定可以用非遞歸算法實現(xiàn) 。 ? 編寫遞歸程序的關(guān)鍵 ◆ 建立遞推公式 ◆ 遞歸結(jié)束條件 是保證遞歸可以正常結(jié)束的前提 遞歸 討論 編寫數(shù)值型遞歸程序 ? 求菲波那奇序列： 1， 1， 2， 3， 5， 8， 13， 21， …… 建立問題的遞歸定義： f(n)=1 當 n=1或 n=2 時 f(n)=f(n1)+f(n2) 當 n2 時 程序： f ( n ) int n。 { if (n==1||n==2) return (1)。 /* 結(jié)束條件 */ else return ( f(n1) + f(n2) )。 } ? 請用遞歸的方法計算下列函數(shù)的值： px(x,n) = x x2 + x3 x4 + ...... (1)n1xn n0 已知程序： double px ( x, n ) int n。 double x。 { if (n==1) return ( )。 else return ( x * ) 。 } 請?zhí)顚戇m當?shù)恼Z句 ， 使之成為正確的程序 。 編寫數(shù)值型遞歸程序 ? 分析： px(x,n)= x x2 + x3 x4 + ...... (1)n1xn n0 = x * ( 1 x + x2 x3 + ...... (1)n1xn1 ) = x * ( 1 (x x2 + x3 ...... (1)n2xn1 )) = x * ( 1 px(x,n1) ) 可將原來的非遞歸定義形式轉(zhuǎn)化為等價的遞歸定義： px(x,n) = x 當 n=1 時 px(x,n) = x * ( 1 px(x,n1) ) 當 n1 時 ? 程序： double px ( x, n ) int n。 double x。 { if (n==1) return ( )。 else return ( x * ) 。 } x ( 1 px(x,n1) ) 編寫數(shù)值型遞歸程序 ? 非數(shù)值型問題的遞歸求解一般方法 。 此時 ， 求解的方法一定是非遞歸的算法 ， 而且十分簡單 。 （ 或多個 ） 小問題 ，且每個分解后的小問題與原來的問題仍然是相似的 ，具有相同的性質(zhì) ， 只是在問題的規(guī)模上有所縮小 。 思路類似于“數(shù)學(xué)歸納法” 編寫非數(shù)值型遞歸程序 ?編制求最大公約數(shù)的遞歸函數(shù) q(a,b)（ 輾轉(zhuǎn)相除法 ） ?設(shè)兩數(shù) a, b (ba) ?用 b除 a, 得 a=bq+r, r為余數(shù) ?若 r==0,則最大公約數(shù)為 ， 商 q（ 結(jié)束條件 ） ?若 r！ =0,則最大公約數(shù)為 ， 商 b與余數(shù) r的最大公約數(shù) （ 遞歸模型 ） 編寫非數(shù)值型遞歸程序 ? 楊輝三角形 第 8次作業(yè) ? （ 遞歸 ） ? （ 遞歸 ） ? ，編號依次為1～ n,年齡都相差 2歲，且第一個人的年齡是 10歲，問第 n個人的年齡是多大？要求（ 1）通過 函數(shù)遞歸 （ 2） n的值從鍵盤輸入 ? （思考題 1， 遞歸 ） ? （遞歸）
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1