【正文】 */ printf(“var_auto=%d, var_static=%d\n”, var_auto, var_static)。 ++var_auto。 ++var_static。 } void main() { int i。 for(i=0。 i5。 i++) auto_static()。 } 第 77 頁(yè) 在一個(gè)程序中 ， 若存在程序自己調(diào)用自己的現(xiàn)象就是構(gòu)成了遞歸 。 如果函數(shù) funA在執(zhí)行過(guò)程又調(diào)用函數(shù)funA自己 ， 則稱函數(shù) funA 為 直接遞歸 。 如果函數(shù) funA在執(zhí)行過(guò)程中先調(diào)用函數(shù)funB， 函數(shù) funB在執(zhí)行過(guò)程中又調(diào)用函數(shù)funA， 則稱函數(shù) funA為間接遞歸 。 函數(shù)的遞歸 一、遞歸的概念 第 78 頁(yè) 函數(shù)的遞歸（續(xù)） 程 序 為 ： 用遞歸函數(shù)求 n! 已知： n階乘的遞歸定義為： n! = 1 當(dāng) n = 1 時(shí) n! = n * (n1)! 當(dāng) n 1 時(shí) main ( ) { int n, p。 printf (N=?)。scanf (%d, amp。n)。 p = facto (n)。 printf (%d!=%d\n, n, p)。 } facto ( int n ) { int r。 if ( n == 1 ) r = 1。 else r=n*facto(n1)。 /* 遞歸調(diào)用 */ return (r)。} 二、遞歸程序 第 79 頁(yè) 主函數(shù) 第一次 調(diào)用 第二次 第三次 第四次 n=4 p=facto(4) 調(diào)用 └─→ n=4 r=4*facto(3) 調(diào)用 └─→ n=3 r=3*facto(2) 調(diào)用 └─→ n=2 r=2*facto(1) └─→ n=1 ` return(1) ┌←─────┘ 返回 r=2* 1 =2 return(2) ┌←─────┘ 返回 r=3* 2 =6 return(6) ┌←─────┘ 返回 r=4* 6 =24 return(24) ┌←──────┘ 返回 p=24 打印 24 facto (int n ) { int r。 if (n==1) r = 1。 else r=n*facto(n1)。 return (r)。 } 遞歸返回過(guò)程 遞歸調(diào)用過(guò)程 函數(shù)的 遞歸 （續(xù)） 三、遞歸程序的執(zhí)行過(guò)程 第 80 頁(yè) 函數(shù)的 遞歸 （續(xù)） 遞歸調(diào)用的執(zhí)行過(guò)程 facto ( 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)。 } 等價(jià)于 當(dāng) n = 1 時(shí) n! = 1 當(dāng) n 1 時(shí) n! = n * (n1)! 第 81 頁(yè) 函數(shù)的 遞歸 （續(xù)） facto(int n) { int s。 if(n= =0) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } facto(int n) int s。 if(n= =0) facto(int n) { int s。 if(n= =0) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } s=facto(n1) facto(int n) int s。 if(n= =0) facto(int n) { int s。 if(n= =0) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } s=facto(n1) facto(int n) { int s。 if(n= =0) s = 1。 else { s=facto(n1)。 s=n*s。 } return(s)。 } facto(int n) facto(int n) int s。 int s。 if(n= =0) if(n= =0) 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 第 91 頁(yè) ? 遞歸的基礎(chǔ) 語(yǔ)言本身支持遞歸調(diào)用 。 自動(dòng)變量的特點(diǎn) ， 保證了在每層遞歸調(diào)用的過(guò)程中 ， 變量保持相對(duì)于各個(gè)層次的獨(dú)立性 。 遞歸過(guò)程實(shí)際上是一個(gè) 隱含 著循環(huán)的過(guò)程 。 ? 對(duì)遞歸的認(rèn)識(shí) 所有的遞歸問(wèn)題一定可以用非遞歸算法實(shí)現(xiàn)。 優(yōu)點(diǎn)： 對(duì)一些本身已經(jīng)蘊(yùn)涵了遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的問(wèn)題，采用遞歸算法可使 程序簡(jiǎn)潔，可讀性好 。非遞歸算法會(huì)使程序結(jié)構(gòu)非常復(fù)雜。 缺點(diǎn)： 遞歸調(diào)用會(huì) 增加存儲(chǔ)空間和執(zhí)行時(shí)間上的開(kāi)銷(xiāo) 。 遞歸 討論（續(xù)） 第 92 頁(yè) ? 遞歸問(wèn)題的分類(lèi) ◆ 數(shù)值性遞歸問(wèn)題 ◆ 非數(shù)值性遞歸問(wèn)題 對(duì)于不同類(lèi)型的問(wèn)題 ,可以采用不同的解決方法。 ? 編寫(xiě)遞歸程序的關(guān)鍵 ◆ 建立遞歸模型 （ n!=n*(n1)! 問(wèn)題的 遞歸定義 是編寫(xiě)遞歸程序的基礎(chǔ) ◆ 遞歸結(jié)束條件 （ 當(dāng) n=1時(shí) n!=1） 是保證遞歸可以正常結(jié)束的前提 遞歸 討論（續(xù)） 第 93 頁(yè) ? 例 ： 采用遞歸方法計(jì)算 x的 n次方 。 xn = 1 當(dāng) n = 0 時(shí) xn = x * xn1 當(dāng) n 0 時(shí) include main( ) { int x, n。 scanf(%d%d, amp。x, amp。n)。 printf (%d**%d=%d\n, x, n, power(x,n) )。 } power (int x, int n) { if(n==0) return (1)。 /* 遞歸結(jié)束條件 */ else return(x*power( x, n1 ) )。 } 遞歸 下一個(gè)實(shí)例（續(xù)） 練習(xí) 第 94 頁(yè) 1. 編寫(xiě)函數(shù)實(shí)現(xiàn)將十進(jìn)制整數(shù)轉(zhuǎn)換為 2進(jìn)制數(shù)和 16進(jìn)制數(shù)； 2. 編寫(xiě)函數(shù) fun：判斷數(shù) n是否為素?cái)?shù)，通過(guò)調(diào)用 fun實(shí)現(xiàn)求 200以內(nèi)的素?cái)?shù)，并輸出； 3. 漢諾塔問(wèn)題：有 A， B， C三根柱子， n個(gè)大小不一的盤(pán)子放在 A柱上，要求通過(guò) B柱將盤(pán)子最后移動(dòng)到 C柱上，要求在移的過(guò)程中，大盤(pán)不能放在小盤(pán)上。請(qǐng)編寫(xiě)遞歸函數(shù)實(shí)現(xiàn)漢諾塔問(wèn)題，屏幕打印輸出盤(pán)子移動(dòng)方案； 4. 編寫(xiě)遞歸函數(shù)計(jì)算階乘 n！