【文章內(nèi)容簡介】 函數(shù)與編譯預(yù)處理 第 章遞歸方法求 n! 由于 n！ = n*(n1)! 是遞歸定義 所以求 n！ ?（ n1）！ (n1)! ?（ n2）！ (n –2)! ?（ n3）！ …… 1!? 0！的問題， 已知條件為： 0！ =1。 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章遞歸函數(shù)： 1 n=0 f(n)= f(n1)*n n0 遞歸函數(shù)一般形式： 函數(shù)名 f（參數(shù)） { if（ n==初值） 結(jié)果 =….。 else 結(jié)果 =含 f(n1)的表達式 。 return (返回結(jié)果 )； } 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章include int f(int x) { int t。 if(x==0) t=1。/*遞歸出口 */ else t=f (x1)*x。 。/*遞歸公式 */ return(t)。 } main() { int n=0,s。 scanf(%d,n)。 s=f(n)。 printf(%d! =%10d,n,s)。 } 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章f函數(shù)在回推階段被調(diào)用了 4次，遞歸調(diào)用了 3次，到終止條件才有確定的值，然后再遞推出每一次調(diào)用的值，最后得到所求的結(jié)果。 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 例 ： 求 Fibonacci數(shù)列： 打印 1， 1， 2， 3， 5，8， …… 的前 40個數(shù) 。 3)(nFFF2)(n1F1)(n1F2n1nn21?????????大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章include main( ) { long f1, f2 。 int i 。 f1=1 。 f2=1 。 for( i=1。 i20 。 i++ ) { printf(%12ld%12ld ,f1, f2 ) 。 if( i%2==0) printf( \n ) 。 f1= f1 + f2 。 f2= f2 + f1 。 } } 方法 1：用循環(huán)結(jié)構(gòu)來實現(xiàn) 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章include int fib(int n) { int f。 if (n==1||n==2) f=1。 else f=fib(n1)+fib(n2)。 return f。 } main( ) { int i。 for( i=1。 i=40 。 i++ ) { printf(%15d,fib(i))。 if(i%4==0) printf(\n)。} } 方法 2：用遞歸函數(shù)來實現(xiàn) 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 例： 反向輸出一個整數(shù) include main() { int n。 scanf(%d,n)。 if(n0) {n=n。 printf()。 } while(n!=0) {printf(%d,n%10)。 n=n/10。 } } 方法 1：用循環(huán)結(jié)構(gòu)來實現(xiàn) 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章include void main() { void printn(int x)。 int n。 scanf(％ d,n)。 if(n0) { n=n。 putchar(39。39。)。 } printn(n)。 } void printn(int x) /*反向輸出整數(shù) x*/ { if(x=0x=9) /*若 x為一位整數(shù) */ printf(％ d,x)。 /*則輸出整數(shù) x*/ else /*否則 */ { printf(％ d,x％ 10)。 /*輸出 x的個位數(shù)字 */ printn(x/10)。 /*將 x中的個位數(shù)字去掉，形成新的 x后，繼續(xù)遞歸操作 */ } } 方法 2：用遞歸函數(shù)來實現(xiàn) 輸出一個正整數(shù)的遞歸算法為： if(n為一位整數(shù) ) 輸出 n。 else {輸出 n的個位數(shù)字 。 對剩余數(shù)字組成的新整數(shù)重復(fù) 反向輸出 操作 。 } 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章 例 ：漢諾塔問題 。 初始狀態(tài)： 有 3個塔，每個都堆放若干個盤子。開始時，所有盤子均在塔 a上，并且，盤子從上到下，按直徑增大的次序放置 。 要求解決問題： 設(shè)計一個盤子移動的序列，使得塔 a上的所有盤子借助于塔 b移動到塔 c上。 兩個限制： 1）一次只能移動一個盤子； 2）任何時候都不能把盤子放在比它小 的盤子的上面。 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章假設(shè) 塔 a有 n個盤子 已知條件： 若只有一個盤子，則是直接從１移到３ （遞歸出口） 算法設(shè)計如下： ? 第一步：把 n 1個盤子依照題目中的規(guī)則從塔 a（源塔）借助于塔 c（中間塔）搬到塔 b（目標(biāo)塔）。 ? 第二步：將剩下的一只盤（也就是最大的一只）直接從塔 a（源塔）搬到那個仍然空著的塔 c（目標(biāo)塔）。 ? 第三步：再次將 b塔（源塔）上的 n 1個盤子借助于塔 a（中間塔）搬到塔 c（目標(biāo)塔）。這一步是沒有問題的，因為 c塔上僅有一只最大的盤。 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章函數(shù) hanoi(int n,int a,int b,int c)設(shè)計： １．如果 (n==1) 則 a?c。 ２． 否則執(zhí)行３步 21 調(diào)用函數(shù) hanoi(n1,a,c,b)。 22 a?c。 23 調(diào)用函數(shù) hanoi(n1,b,a,c)。 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 例 Hanoi問題 include void hanoi(int n,int a,int b,int c) { if(n==1) printf(%d%d\n,a,c)。 else { hanoi(n1,a,c,b)。 printf(%d%d\n,a,c)。 hanoi(n1,b,a,c)。 } } main() { int n。 printf(Input n:)。 scanf(%d,n)。 hanoi(n,1,2,3)。 } 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章 運行情況如下： input n:3↙ the step: 13 12 32 13 21 23 13 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章先看一個例子 ,錯在那里 ?: include void f1( ) { int t=2。 a *= t。 b /= t。 } main() { int a, b。 scanf(%d,%d, a, b)。 f1( )。 // 調(diào)用函數(shù) f1( ) printf (a=%d,b=%d, a, b)。 } 1 編譯程序會提示出錯 : Undefined symbol ‘a(chǎn)’ 和 Undefined symbol ‘b’ 。 為什么 ? 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章 生存期 ：變量在某一時刻存在 靜態(tài)變量與動態(tài)變量 作用域 ：變量在某區(qū)域內(nèi)有效 局部變量與全局變量 (文件、函數(shù)、復(fù)合語句 ) 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章 變量的存儲類型 (特性 ) :數(shù)據(jù)類型 ,存儲 類型 。 完整的變量定義 : [存儲 類型 ] [數(shù)據(jù)類型 ] 變量名 。 類型 (特性 ) 自動型 auto 靜態(tài)型 static 寄存器型 register 外部型 extern 程序區(qū) 靜態(tài)存儲區(qū) 動態(tài)存儲區(qū) 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章 類型的變量的生存期為程序執(zhí)行的整個過程，在該過程中占有固定的存儲空間，稱它們?yōu)橛谰么鎯?。 static extern 動態(tài)存儲 類型變量 只生存在某一段時間內(nèi) 。例如，函數(shù)的形參和函數(shù)體內(nèi)定義的變量 ,只是在程序進入該函數(shù)時才分配存儲空間 ,當(dāng)該函數(shù)執(zhí)行完后 ， 變量對應(yīng)的存儲空間又被撤銷了。 atuo register 大學(xué) C/C++語言程序設(shè)計 第 6章 函數(shù)與編譯預(yù)處理 第 章– 局部變量與全局變量 ? 局部變量 內(nèi)部變量 –定義：在 函數(shù)內(nèi) 或 復(fù)合語句 定義 –說明： 187。main（函數(shù)） 中定義的變量只在 main（函數(shù)）中有效 。 187。復(fù)合語句 中定義的變量只在 復(fù)合語句 中有效 。 187。不同函數(shù)中同名變量，占不同內(nèi)存單元 。 187。形參屬于局部變量 。 187。局部變量可用存儲類型 ： auto register。 static （ 默認(rèn)為 auto） float f1(int a) { int b,c。 ……. } char f2(int x,int y) { i