【文章內(nèi)容簡介】 star(int d) { int i。 for(i=1。id。i++) if (i10) line()。 else printf(*)。 } void line() { printf()。} 2)4()5(?? ageage2)3()4(?? ageage2)2()3(?? ageage2)1()2(?? ageage10)1(?age12)2(?age14)3(?age16)4(?age18)5(?age回推 遞推 例 11年齡問題 :有 5個人坐在一起，問第 5個人多少歲？他說比 第4個人大 2歲 。問第 4個人多少歲，他說比 第 3個人大 2歲 。問第 3個人多少歲，又說比第 2個人大 2歲 。問第 2個人，說比 第 1個人大 2歲 。最后問第 1個人， 他說是 10歲 。請問第 5個人多少歲。 ?)(nage)1(2)1()1(10????Nnagen遞歸調(diào)用 ——一個函數(shù)在它的函數(shù)體內(nèi)直接或者間接調(diào)用 它自身 。這種函數(shù)稱為遞歸函數(shù)。 ? 要解決的問題可以轉(zhuǎn)換為一個新的問題，而這個新的問題的解決與原來問題的解法相同，只是所處理的對象有規(guī)律的變化，遞增或遞減。 ? 可以應(yīng)用這個規(guī)律的遞歸結(jié)束條件 ? 要有一個明確的遞歸結(jié)束條件 算法描述為： if(遞歸中止條件 ) return (條件終止時的值 ) else return 遞歸公式 include int age(int n) { int c。 if(n==1) c=10。 else c=age(n1)+2。 return(c)。 } void main() { printf(%d\n,age(5))。 } 遞歸終止條件 遞歸公式 main age(5) age(4) age(3) age(2) age(1) end 例 12： 用遞歸法計算 n! 分析 ： 用遞歸法計算 n!可用下述公式表示： n!=1 (n=0,1) n!=n (n1)! (n1) long ff (int n) { long f。 if(n0) printf(n0,input error)。 else if(n==0||n==1) f=1。 else f=ff(n1)*n。 return(f)。 } include void main() { long ff(int)。 int a。 printf(a=)。 scanf(%d,amp。a)。 printf(%d!=%ld\n,a,ff(a))。 } 例 13 Hanoi(漢諾塔）問題 ：這是一個古典的數(shù)學(xué)問題，是一個只有用遞歸方法（而不能用其他方法）解決的問題。問題是這樣的：古代有一個梵塔，塔內(nèi)有 3個座 A、B、 C，開始時 A座上有 64個盤子，盤子大小不等，大的在下，小的在上。有一個老和尚想把這 64個盤子從 A座移到 C座上，但每次只允許移動一個盤子，且在移動過程中在 3個坐上都始終保持大盤在下，小盤在上。在移動過程中可以利用 B座，要求編程打印出移動的步驟。 1 2 3 1 2 3 hanoi(int n,char one,char two,char three) n==1 move(one,three) move(one,three) hanoi(n1,one,three,two) hanoi(n1,two,one,three) T F move(char x,char y) printf(“%c%c\n”,x,y)。 例 13 Hanoi(漢諾塔）問題： include void move(char x,char y){ printf(%c%c\n,x,y)。} void hanoi(int n,char one,char two,char three) { if(n==1) move(one,three)。 else{ hanoi(n1,one,three,two)。 move(one,three)。 hanoi(n1,two,one,three)。 } } void main() { int m。 printf(input the number of disks:)。 scanf(%d,amp。m)。 printf( the step to moving %3d diskes:\n,m)。 hanoi(m,39。A39。,39。B39。,39。C39。)。 } 對遞歸函數(shù)概括如下： ? 有些問題既可以用遞歸的方法解決，也可以用遞推的方法解決。有些問題不用遞歸是難以得到結(jié)果的。 ? 遞歸函數(shù)算法清晰，代碼簡練 ? 從理論上講，遞歸函數(shù)似乎很復(fù)雜，其實它是編程中的一類問題的算法，最為直接 ? C編譯系統(tǒng)對遞歸函數(shù)的自調(diào)用次數(shù)沒有限制，但當(dāng)遞歸層次過多時，可能會引起內(nèi)存不足而造成運行出錯，尤其時函數(shù)內(nèi)部定義較多的變量和較大的數(shù)組時 采用遞歸方式實現(xiàn) 二分查找 ? 函數(shù)調(diào)用時，實參和形參類型不一致 ? 在值傳遞中，企圖用形參值的改變影響實參值 ? 傳遞數(shù)據(jù)名時傳遞為數(shù)組元素值 ? 對函數(shù)進行嵌套定義 ? 對函數(shù)遞歸調(diào)用時，落掉遞歸結(jié)束條件 ? 在 C語言中，參數(shù)的值傳遞，具有如下特點： ① 實參與形參各自占據(jù)獨立的存儲單元； ② 調(diào)用時，將實參的值傳入形參單元 ； ③ 在被調(diào)用的函數(shù)內(nèi)，訪問相應(yīng)的形參單元 ；④ 函數(shù)調(diào)用結(jié)束時，釋放形參單元 ? 參數(shù)的地址傳遞有什么特點？ ? C語言中，函數(shù)可以嵌套調(diào)用，不可以嵌套定義 ? 函數(shù)遞歸調(diào)用指對函數(shù)自身的調(diào)用，算法描述為： if(遞歸中止條件 ) return (條件終止時的值 ) else return 遞歸公式 教學(xué)內(nèi)容 變量的作用域與存儲類別、內(nèi)部函數(shù)和外部函數(shù) 教學(xué)目標(biāo) 應(yīng)知 變量的作用域與生存期 變量的存儲類別 宏定義和文件包含 程序中變量的作用范圍 能夠分析程序中靜態(tài)變量的值 會正確使用宏定義 難點 靜態(tài)變量在程序中的作用 ? 變量 ——變量是對程序中數(shù)據(jù)的存儲空間的抽象 靜態(tài)存儲方式 動態(tài)存儲方式 自動型 (auto) 靜態(tài)型 (static) 寄存器型 (registic) 外部型 (extern) 指在程序運行期間由系統(tǒng)分配 固定的 存儲空間的方式 指在程序運行期間由系統(tǒng) 根據(jù)需要進行動態(tài)分配存儲空間的方式 int sum。 auto int a,b,c。 register int i。 static float x,y。 將變量分為 int、float等等類型 全局變量 局部變量 指在程序 整個運行期間 都起作用 指在程序 局部運行期間 都起作用 數(shù)據(jù)類型： 變量所持有的數(shù)據(jù)的性質(zhì)（操作屬性） 生存期： 變量在內(nèi)存中存在的某一時間范圍（數(shù)據(jù)的存儲類別） 作用域： 變量能夠起作用的程序空間范圍 int f1(int a,int b) { int c,d。 ...... } float f2(float x,float y) { int c,d。 { float t。 ...... } ...... } main() { int x,y。float a,b。 ...... } 局部變量： 函數(shù)內(nèi)部或復(fù)合語句內(nèi) 定義的變量是局部變量，也稱為內(nèi)部變量。 a,b,c,d在此范圍內(nèi)有效 x,y,c,d在此范圍內(nèi)有效 t在此范圍內(nèi)有效 x,y,a,b在此范圍內(nèi)有效 ? 主函數(shù)定義的變量，也只在主函數(shù)內(nèi)有效。主函數(shù)也不能使用其他函數(shù)中定義的變量，從這一點上講，函數(shù)都是平等的。 ? 不同函數(shù)中變量可以同名，互不干擾。 ? 形參也是局部變量 ? 在復(fù)合語句中也可定義變量，它們的作用域同樣只在所定義的段落內(nèi)部。 全局變量： 函數(shù)之外定義的變量叫全局變量，也稱為外部變量。 說明： 全局變量從 定義處開始起作用，直到整個源文件結(jié)束 ，此后出現(xiàn)的函數(shù)都可使用。它實際上實現(xiàn)了函數(shù)之間數(shù)據(jù)溝通的方式，增強了各模塊的聯(lián)系。但也降低了模塊自身的獨立性。 int p=1,q=5。 /*全局變量 p,q*/ float f1(int a)/*p,q從此處開始作用且作用域一直延續(xù)到程序結(jié)束 */ { int b,c。 …… } char c1,c2。 /*外部變量 c1,c2，它們從這里 開始發(fā)揮作用 */ char f2(x,y) /*定義函數(shù) f2*/ { char c1,c2。 /*注意此處的局部變量 c1,c2將 屏蔽外層的全局變量，即，在 f2函數(shù)中凡是提到 c1,c2，均是 指的局部變量 c1,c2*/ …… } include int x=2,y=3。 void main() { void swap()。 swap()。 printf(交換后 :\n)。 printf(x=%d,y=%d\n, x,y)。 } void swap() { int temp。 temp=x。 x=y。 y=temp。 } x=10。y=5。 例 14:使用全局變量實現(xiàn)兩個整型數(shù)值的交換。 ? 限制了函數(shù)的通用性 ? 損害了程序的清晰度 ? 降低了內(nèi)存的利用率 如果在同一個源文件中，外部變量與局部變量同名，則在局部變量的范圍內(nèi)， 外部變量被“屏蔽” 動態(tài)存儲方式 ： 程序運行期間據(jù)需要動態(tài)分配存儲空間的方式。 靜態(tài)存儲方式： 在程序運行期間分配固定存儲空間的方式。 動態(tài)存儲區(qū) 靜態(tài)存儲區(qū) 程序區(qū) ? 數(shù)據(jù)分別存放在靜態(tài)存儲區(qū)和動態(tài)存儲區(qū) ? 全局變量全部存放在靜態(tài)存儲區(qū) 中，在程序開始執(zhí)行時給全局變量分配存儲區(qū)，程序執(zhí)行完畢就釋放。在程序執(zhí)行過程中它們占據(jù)固定的存儲單元，而不是動態(tài)地進行分配和釋放 ? 在 動態(tài)存儲區(qū)中 存放以下數(shù)據(jù)： 函數(shù)形式參數(shù) 、 自動變量 、 函數(shù)調(diào)用時的現(xiàn)場保護和返回地址 等。對以上這些數(shù)據(jù)，在函數(shù)調(diào)用開始時分配動態(tài)存儲空間，函數(shù)結(jié)束時釋放這些空間。 ? 在 復(fù)合語句內(nèi) 或 函數(shù)內(nèi) 定義變量時，使用atuo說明符或省略存儲類型說明符，所定義的變量就是 auto變量。 ? auto類型的局部變量 存儲在動態(tài)存儲區(qū) ，動態(tài)分配存儲空間，可以節(jié)省存儲空間。 ? auto變量使用說明： ? 同一函數(shù)的兩次調(diào)用之間，不保留值。 ? 自動變量如定義時賦初值 (在執(zhí)行階段 )，則每次調(diào)用函數(shù)都賦一次初值。 ? static 類型的靜態(tài)變量： 存儲在靜態(tài)存儲區(qū) ，靜態(tài)分配存儲空間， 其生存期為整個程序的運行區(qū)間 。 ? 對靜態(tài)變量是 在編譯時 賦初值的，即只賦初值一次 ? 如在定義局部變量時不賦初值的話，則 對靜態(tài)變量 來說，編譯時自動賦初值 0或空字符 。而對 自動變量 而言，如果不賦初值 它就是一個不確定的值 include void main() { int x。 static y。 printf(x=%d,y=%d\n,x,y)。 } include void main() { int f(int)。 int a=2,i。 for(i=0。i3。i++) printf(%d,f(a))。 } int f(int a) { auto int b=0。 static int c=3。 b=b+1。 c=c+1。 return(a+b+c)。 } 調(diào)用時的初值 調(diào)用后的初值 b c b c a+b+c 0 3 1 4 7 0 4 1 5 8 0 5 1 6 9 register類型的局部變量也屬于 auto變量。 其區(qū)別在于 :用register說明的變量建議編譯程序?qū)⒆兞康闹荡娣旁?CPU的寄存器中，而不是內(nèi)存中。存取速度最快，適用于使用頻繁的變量，但受寄存器數(shù)目的限制。 include void main()