C++函數(shù)、遞推、遞歸

《C++語言程序設(shè)計》講函數(shù)、遞推、遞歸2021/5/91第九講——函數(shù)、遞推、遞歸遞推遞推是計算機(jī)數(shù)值計算中的一個重要算法。思路：通過數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡單運(yùn)算，以充分發(fā)揮計算機(jī)長于重復(fù)運(yùn)算的特點(diǎn)；遞推法特點(diǎn)：從一個已知的事實出發(fā)，按一定規(guī)律推出下一個事實，再從這個新的已知事實出發(fā)，再向下推出一個新的事實。2021/5/92大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞推舉例（1）例:(猴子吃桃問題)猴子第1天摘下若干桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個。第2天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半另加一個。到第10天早上想再吃時，就只剩下一個桃子了。問第1天猴子共摘了多少桃子？2021/5/93大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸解題思路：假設(shè)用S(i) 表示第i 天沒吃之前的桃子數(shù)目；則S(1)即為第1 天所摘的桃子數(shù)；S(10)=S(9)*1/2– 1 第 10天沒吃之前的桃子數(shù)S(2)=S(1)*1/2–1第2天沒吃之前的桃子數(shù)S(3)=S(2)*1/2- 1第3天沒吃之前的桃子數(shù)……S(9)=S(8)*1/2-1第9天沒吃之前的桃子數(shù)2021/5/94大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸一般形式：S(i)=S(i-1)*1/2–1,i=2,3,…,10;這個公式可用于知第1天沒吃之前的桃子數(shù)推算第2天沒吃之前的，再推算第3天沒吃之前的，…….?，F(xiàn)在要求的是第1天沒吃之前的。能否倒過來，先知第10天沒吃之前的的再反推第9天沒吃之的，……，直到第1天沒吃之前的。為此將上式改寫為：S(i-1)=2*(S(i)+1),i=10,9,8,…,22021/5/95大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸程序：大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部

62021/5/96第九講——函數(shù)、遞推、遞歸分析：一般形式：S(i-1)=2*(S(i)+1),i=10,9,8,…,2;初始：s2=1; //S(10)=1i=9s1=2*(s2+1);s2= s1;s1=2*(s2+1);s2= s1;s1=2*(s2+1);s2= s1;//S(9)=2*(S(10)+1)// s2=s1=S(9)//S(8)=2*(S(9)+1)// s2=s1=S(8)//S(7)=2*(S(8)+1)// s2=s1=S(7)i=8i=7i=6s1=2*(s2+1);s2= s1;//S(6)=2*(S(7)+1)// s2=s1=S(6)2021/5/97大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸i=5s1=2*(s2+1);s2= s1;//S(5)=2*(S(6)+1)// s2=s1=S(5)//S(4)=2*(S(5)+1)// s2=s1=S(4)//S(3)=2*(S(4)+1)// s2=s1=S(3)//S(2)=2*(S(3)+1)// s2=s1=S(2)//S(1)=2*(S(2)+1)// s2=s1=S(1)i=4s1=2*(s2+1);s2= s1;s1=2*(s2+1);s2= s1;s1=2*(s2+1);s2= s1;s1=2*(s2+1);s2= s1;i=3i=2i=12021/5/98大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞推舉例（2）遞推數(shù)列一個數(shù)列從某一項起，它的任何一項都可以用它前面的若干項來確定，這樣的數(shù)列稱為遞推數(shù)列，表示某項與其前面的若干項的關(guān)系就稱為遞推公式。例如自然數(shù)1,2，…,n的階乘就可以形成如下數(shù)列：1！，2！，3！，…,(n-1)!,n!另fact(n)為n階乘，依據(jù)后項與前項的關(guān)系可以寫出遞推公式： fact(n)=n*fact(n-1)(通項公式)fact(1)=1 （邊界條件）2021/5/99大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞推算例（3）遞推算法程序?qū)崿F(xiàn)：有了通項公式和邊界條件后，采用循環(huán)結(jié)構(gòu)，從邊界條件出發(fā)，利用通項公式通過若干步遞推過程就可以求出結(jié)果；例：王小二自稱刀工不錯，有人放一張大的煎餅在砧板上，問他：“餅不許離開砧板，切100刀最多能分成多少塊？”2021/5/910大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸分析：切一刀切二刀切三刀 切四刀令q(n)表示切n 刀能分成的塊數(shù)，由上圖可知q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1+2+3+4=112021/5/911大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸分析：切一刀切二刀切三刀 切四刀在切法上是讓每兩條線都有交點(diǎn)。用歸納法可得出q(n)=q(n-1)+nq(0)=1(邊界條件)2021/5/912大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞推算例（3）參考程序：2021/5/913大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸遞歸算法在可計算理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。就遞歸算法而言不涉及高深數(shù)學(xué)知識，只不過初學(xué)者建立起遞歸概念不太容易?？匆粋€簡單的例子：2021/5/914大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸有 5個人坐在一起，問第5個人多少歲？他說比第4 個人大兩歲。問第 4個人歲數(shù)，他說比第3個人大兩歲。問第3個人，又說比第2 個人大兩歲。問第2 個人，說比第1 個人大兩歲。最后問第1 個人，他說是10 歲。請問第5個人多大？解題思路：假設(shè)用age(i) 表示第i 個人的歲數(shù)，則借助循環(huán)結(jié)構(gòu)采用遞推方法求解！age(5)=age(4)+2;age(4)age(3)==age(3)age(2)++2;2;age(2)=age(1)+2;age(1)=10;2021/5/915大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸一般形式：age(n)=10age(n)=age(n-1)+2(n=1)(n>2)2021/5/916大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸分析：上述求解是從求解目標(biāo)出發(fā)，即將第n個人的年齡表示第(n-1)個人的年齡，再回溯到第（n-2）個人的年齡……直到第1個人的年齡；（回溯階段）然后，采用遞推方法，從第1個人的已知年齡推算第2個人的年齡，在推算第3 個人的年齡，直到推算出第5 個人的年齡；（遞推階段）這是一個遞歸問題，對它的求解可以分成回溯和遞推兩個階段；顯而易見，如果不希望遞歸過程無限制的進(jìn)行下去，必須有一個結(jié)束遞歸過程的條件；如：age(1)=102021/5/917大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸計算年齡函數(shù)：intage(intn){intc;if(n==1) { c=10;}else{c=age(n-1)+2;}returnc;}2021/5/918大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸調(diào)用在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，稱為函數(shù)的遞歸（recursive）調(diào)用;C++允許函數(shù)的遞歸調(diào)用；例：intf(intx){inty,z;z=f(y);return2*z;}2021/5/919大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸調(diào)用直接調(diào)用間接調(diào)用注意：上述兩種情況都是無終止的自身調(diào)用；顯然，程序中不應(yīng)該出現(xiàn)這種無終止的調(diào)用，而只應(yīng)出現(xiàn)有限次的，有終止的遞歸調(diào)用；可以用if語句控制，實現(xiàn)遞歸調(diào)用結(jié)束；2021/5/920大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸函數(shù)包含遞歸調(diào)用的函數(shù)，稱為遞歸函數(shù)；計算年齡函數(shù):intage(intn){intc;if(n==1) { c=10;}else{c=age(n-1)+2;}returnc;}2021/5/921大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸函數(shù)計算年齡遞歸函數(shù)執(zhí)行過程：age(5)=age(4)+2//c=age(4)+2=age(3)+2+2//c=age(3)+2=age(2)+2+2+2//c=age(2)+2=age(1)+2+2+2+2；//c=10;2021/5/922大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸計算年齡程序2021/5/923大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸算例（2）用遞歸方法計算n!算法思路：若n=10,則n!=10*9!定義函數(shù)fact(n)表示計算n！的函數(shù)，則有fact(n)=n*fact(n-1),n>1fact(n)=1,n=0,n=1;2021/5/924大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸算例（2）階乘計算遞歸函數(shù)：iinnttffaacctt((iinnttnn)){{intc;if(cn==n=*0f||anct=(n=-11));c=1;reelstuernc;c=n*fact(n-1);returnc;}}結(jié)束遞歸條件2021/5/925大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸算例（3）用遞歸函數(shù)計算組合數(shù)：C(m,n)，即從m個數(shù)中取n個數(shù)的組合數(shù)；C(m,n)=C(m-1,n)+C(m-1,n-1);C(m,n)=0,m<0,n<0;C(m,n)=1,m==n;C(m,n)=m,n=1;2021/5/926大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸算例（3）2021/5/927大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸算例（4）例:(猴子吃桃問題)猴子第1天摘下若干桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個。第2天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半另加一個。到第10天早上想再吃時，就只剩下一個桃子了。問第1天猴子共摘了多少桃子？2021/5/928大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸解題思路：假設(shè)用S(i) 表示第i 天沒吃之前的桃子數(shù)目；則S(1)即為第1 天所摘的桃子數(shù)；S(10)=S(9)*1/2– 1 第 10天沒吃之前的桃子數(shù)S(2)=S(1)*1/2–1第2天沒吃之前的桃子數(shù)S(3)=S(2)*1/2- 1第3天沒吃之前的桃子數(shù)……S(9)=S(8)*1/2-1第9天沒吃之前的桃子數(shù)2021/5/929大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸一般形式：S(i)=S(i-1)*1/2–1,i=2,3,…,10;這個公式可用于知第1天沒吃之前的桃子數(shù)推算第2天沒吃之前的，再推算第3天沒吃之前的，…….。現(xiàn)在要求的是第1天沒吃之前的。能否倒過來，先知第10天沒吃之前的的再反推第9天沒吃之的，……，直到第1天沒吃之前的。為此將上式改寫為：2021/5/930大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸一般形式：S(i-1)=2*(S(i)+1),i=2,3,4，…，10則S(1)即為第1 天所摘的桃子數(shù)；S(1)=2*（S(2)+1）S(2)=2* （S(3)+1）…S(8)=2*（S(9)+1）S(10)=12021/5/931大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸函數(shù)：intcount(intn){intc;if(n==10)c=1;elsec=2*(count(n+1)+1);returnc;}這樣可以嗎？有沒有問題？如果出現(xiàn)調(diào)用語句：count(11)?2021/5/932大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸函數(shù)：intcount(intn){intc;if(n>10)return-1;if(n==10)c=1;elsec=2*(count(n+1)+1);returnc;}2021/5/933大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸遞歸方法遞歸實現(xiàn)：在時間和空間上的開銷比較大；但符合人們的思路，程序容易理解；遞歸函數(shù)：只須寫出遞歸公式和遞歸結(jié)束條件（即邊界條件），即可很容易寫出遞歸函數(shù)；2021/5/934大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸局部變量和全局變量一個程序可以包括若干個源程序文件（文件模塊）；每個源程序文件又包括若干個函數(shù)；在每個函數(shù)中和函數(shù)外都可以定義變量。這些在不同地方定義的變量是否都在程序的全部范圍內(nèi)有效？如果不是，他們的有效范圍是什么呢？2021/5/935大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸局部變量和全局變量局部變量在一個函數(shù)內(nèi)部定義的變量是內(nèi)部變量，它只在本函數(shù)范圍內(nèi)有效，換句話說只有在本函數(shù)內(nèi)才能使用它們，在此函數(shù)之外是不能使用這些變量的。同樣的，在復(fù)合語句中定義的變量只在復(fù)合語句內(nèi)范圍內(nèi)有效。2021/5/936大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸floatf1(inta){//函數(shù)f1intb,c;┆}charf2(int{inti,j;┆}intmain(){intm,n;┆{intp,q;┆}}b、c有效a有效x,inty)i、j有效//函數(shù)f2x、y有效//主函數(shù)p、q在復(fù)合語句中有效m、n有效2021/5/937大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸a也只在f1函數(shù)中有效。其他函數(shù)不能調(diào)用。大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部說明：(1)主函數(shù)main中定義的變量(m,n)也只在主函數(shù)中有效,不會因為在主函數(shù)中定義而在整個文件或程序中有效。主函數(shù)也不能使用其他函數(shù)中定義的變量。(2)不同函數(shù)中可以使用同名的變量,它們代表不同的對象,互不干擾。例如,在f1函數(shù)中定義了變量b和c,倘若在f2函數(shù)中也定義變量b和c,它們在內(nèi)存中占不同的單元,不會混淆。(3)可以在一個函數(shù)內(nèi)的復(fù)合語句中定義變量,這些變量只在本復(fù)合語句中有效,這種復(fù)合語句也稱為分程序或程序塊。(4)形式參數(shù)也是局部變量。例如f1函數(shù)中的形參2021/5/938第九講——函數(shù)、遞推、遞歸(5)在函數(shù)聲明中出現(xiàn)的參數(shù)名，其作用范圍只在本行的括號內(nèi)。實際上，編譯系統(tǒng)對函數(shù)聲明中的變量名是忽略的，即使在調(diào)用函數(shù)時也沒有為它們分配存儲單元。例如intmax(inta,intb);┆intmax(intx,int y){cout<<x<<y<<endl;cout<<a<<b<<endl;}//函數(shù)聲明中出現(xiàn)a、b//函數(shù)定義，形參是x、y//合法，x、y在函數(shù)體中有效//非法，a、b在函數(shù)體中無效編譯時認(rèn)為max函數(shù)體中的a和b未經(jīng)定義。2021/5/939大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸全局變量程序的編譯單位是源程序文件（.cpp）,一個源文件可以包含一個或若干個函數(shù)。在函數(shù)內(nèi)定義的變量是局部變量,而在函數(shù)之外定義的變量是外部變量，稱為全局變量(globalvariable,也稱全程變量)。全局變量的有效范圍為從定義變量的位置開始到本源文件結(jié)束。如2021/5/940大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸intp=1,q=5;//全局變量floatf //定義函數(shù)f11(a)inta;圍全局變量c1、c2的作用范圍(inta){intb,c;┆}charc1,c2;charf2(intx,inty)//定義函數(shù)f2{inti,j;┆}main()//主函數(shù){intm,n;┆}2021/5/941大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸p、q、c1、c2都是全局變量，但它們的作用范圍不同，在main函數(shù)和f2函數(shù)中可以使用全局變量p、q、c1、c2，但在函數(shù)f1中只能使用全局變量p、q，而不能使用c1和c2。在一個函數(shù)中既可以使用本函數(shù)中的局部變量，又可以使用有效的全局變量。說明：(1)設(shè)全局變量的作用是增加函數(shù)間數(shù)據(jù)聯(lián)系的渠道。(2)建議不在必要時不要使用全局變量，因為：①全局變量在程序的全部執(zhí)行過程中都占用存儲單元，而不是僅在需要時才開辟單元。2021/5/942大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸②在程序設(shè)計中，在劃分模塊時要求模塊的內(nèi)聚性強(qiáng)、與其他模塊的耦合性弱。即模塊的功能要單一（不要把許多互不相干的功能放到一個模塊中），與其他模塊的相互影響要盡量少，而用全局變量是不符合這個原則的。一般要求把程序中的函數(shù)做成一個封閉體，除了可以通過“實參——形參”的渠道與外界發(fā)生聯(lián)系外，沒有其他渠道。這樣的程序移植性好，可讀性強(qiáng)。2021/5/943大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部

44③使用全局變量過多，會降低程序的清晰性。在各個函數(shù)執(zhí)行時都可能改變?nèi)肿兞康闹?，程序容易出錯。因此，要限制使用全局變量。(3)如果在同一個源文件中，全局變量與局部變量同名，則在局部變量的作用范圍內(nèi)，全局變量被屏蔽，即它不起作用。變量的有效范圍稱為變量的作用域(scope)。歸納起來，變量有4種不同的作用域:文件作用域(filescope)、函數(shù)作用域(functionscope)、塊作用域(blockscope)和函數(shù)原型作用域(functionprototypescope)。文件作用域是全局的，其他三者是局部的。2021/5/944第九講——函數(shù)、遞推、遞歸變量的存儲類別已介紹了變量的一種屬性——作用域，作用域是從空間的角度來分析的，分為全局變量和局部變量。變量還有另一種屬性——存儲期(storageduration，也稱生命期)。存儲期是指變量在內(nèi)存中的存在時間。這是從變量值存在的時間角度來分析的。存儲期可以分為靜態(tài)存儲期(staticstorageduration)和動態(tài)存儲期(dynamicstorageduration)。這是由變量的靜態(tài)存儲方式和動態(tài)存儲方式?jīng)Q定的。2021/5/945大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸存儲方式靜態(tài)存儲方式是指在程序運(yùn)行期間，系統(tǒng)對變量分配固定的存儲空間。動態(tài)存儲方式則是在程序運(yùn)行期間，系統(tǒng)對變量動態(tài)地分配存儲空間。2021/5/946大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸存儲方式先看一下內(nèi)存中的供用戶使用的存儲空間的情況。這個存儲空間可以分為三部分，即：(1)程序區(qū)(2)靜態(tài)存儲區(qū)(3)動態(tài)存儲區(qū)2021/5/947大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸靜態(tài)存儲區(qū)數(shù)據(jù)分別存放在靜態(tài)存儲區(qū)和動態(tài)存儲區(qū)中。全局變量全部存放在靜態(tài)存儲區(qū)中，在程序開始執(zhí)行時給全局變量分配存儲單元，程序執(zhí)行完畢就釋放這些空間。在程序執(zhí)行過程中它們占據(jù)固定的存儲單元，而不是動態(tài)地進(jìn)行分配和釋放。2021/5/948大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸動態(tài)存儲區(qū)在動態(tài)存儲區(qū)中存放以下數(shù)據(jù)：①函數(shù)形式參數(shù)。在調(diào)用函數(shù)時給形參分配存儲空間。②函數(shù)中的自動變量（未加static聲明的局部變量，詳見后面的介紹）。③函數(shù)調(diào)用時的現(xiàn)場保護(hù)和返回地址等。對以上這些數(shù)據(jù)，在函數(shù)調(diào)用開始時分配動態(tài)存儲空間，函數(shù)結(jié)束時釋放這些空間。在程序執(zhí)行過程中，這種分配和釋放是動態(tài)的，如果在一個程序中兩次調(diào)用同一函數(shù)，則要進(jìn)行兩次分配和釋放，而兩次分配給此函數(shù)中局部變量的存儲空間地址可能是不相同的。2021/5/949大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸50大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部如果在一個程序中包含若干個函數(shù)，每個函數(shù)中的局部變量的存儲期并不等于整個程序的執(zhí)行周期，它只是整個程序執(zhí)行周期的一部分。根據(jù)函數(shù)調(diào)用的情況，系統(tǒng)對局部變量動態(tài)地分配和釋放存儲空間。在C++中變量除了有數(shù)據(jù)類型的屬性之外，還有存儲類別(storageclass)的屬性。存儲類別指的是數(shù)據(jù)在內(nèi)存中存儲的方法。存儲方法分為靜態(tài)存儲和動態(tài)存儲兩大類。具體包含4種：自動的(auto)、靜態(tài)的(static)、寄存器的(register)和外部的(extern)。根據(jù)變量的存儲類別，可以知道變量的作用域和存儲期。2021/5/950第九講——函數(shù)、遞推、遞歸自動變量函數(shù)中的局部變量，如果不用關(guān)鍵字static加以聲明，編譯系統(tǒng)對它們是動態(tài)地分配存儲空間的。函數(shù)的形參和在函數(shù)中定義的變量(包括在復(fù)合語句中定義的變量)都屬此類。在調(diào)用該函數(shù)時，系統(tǒng)給形參和函數(shù)中定義的變量分配存儲空間，數(shù)據(jù)存儲在動態(tài)存儲區(qū)中。在函數(shù)調(diào)用結(jié)束時就自動釋放這些空間。如果是在復(fù)合語句中定義的變量，則在變量定義時分配存儲空間，在復(fù)合語句結(jié)束時自動釋放空間。因此這類局部變量稱為自動變量(autovariable)。2021/5/951大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用register聲明寄存器變量

一般情況下，變量的值是存放在內(nèi)存中的。當(dāng)程序中用到哪一個變量的值時，由控制器發(fā)出指令將內(nèi)存中該變量的值送到CPU中的運(yùn)算器。經(jīng)過運(yùn)算器進(jìn)行運(yùn)算，如果需要存數(shù)，再從運(yùn)算器將數(shù)據(jù)送到內(nèi)存存放。如圖所示。為提高執(zhí)行效率，C++允許將局部變量的放在CPU中的寄存器中，需要用時直接從寄存器取出參加運(yùn)算，不必再到內(nèi)存中去存取。這種變量叫做寄存器變量，用關(guān)鍵字register作聲明。但是，是建議性的；值2021/5/952大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用static聲明靜態(tài)局部變量有時希望函數(shù)中的局部變量的值在函數(shù)調(diào)用結(jié)束后不消失而保留原值，即其占用的存儲單元不釋放，在下一次該函數(shù)調(diào)用時，該變量保留上一次函數(shù)調(diào)用結(jié)束時的值。這時就應(yīng)該指定該局部變量為靜態(tài)局部變量(staticlocalvariable)。2021/5/953大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸2021/5/954大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸先后3次調(diào)用f函數(shù)時，b和c的值如書中表所示。2021/5/955大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸靜態(tài)局部變量說明(1)靜態(tài)局部變量在靜態(tài)存儲區(qū)內(nèi)分配存儲單元。在程序整個運(yùn)行期間都不釋放。而自動變量（即動態(tài)局部變量）屬于動態(tài)存儲類別，存儲在動態(tài)存儲區(qū)空間(而不是靜態(tài)存儲區(qū)空間)，函數(shù)調(diào)用結(jié)束后即釋放。(2)為靜態(tài)局部變量賦初值是在編譯時進(jìn)行值的，即只賦初值一次，在程序運(yùn)行時它已有初值。以后每次調(diào)用函數(shù)時不再重新賦初值而只是保留上次函數(shù)調(diào)用結(jié)束時的值。而為自動變量賦初值，不是在編譯時進(jìn)行的，而是在函數(shù)調(diào)用時進(jìn)行，每調(diào)用一次函數(shù)重新給一次初值大連，理工相大學(xué)當(dāng)盤錦校于區(qū)基執(zhí)礎(chǔ)教行學(xué)部一次賦值語句。562021/5/956第九講——函數(shù)、遞推、遞歸(3)如果在定義局部變量時不賦初值的話，對靜態(tài)局部變量來說，編譯時自動賦初值0(對數(shù)值型變量)或空字符(對字符型變量)。而對自動變量來說，如果不賦初值，則它的值是一個不確定的值。這是由于每次函數(shù)調(diào)用結(jié)束后存儲單元已釋放，下次調(diào)用時又重新另分配存儲單元，而所分配的單元中的值是不確定的。(4)雖然靜態(tài)局部變量在函數(shù)調(diào)用結(jié)束后仍然存在，但其他函數(shù)是不能引用它的，也就是說，在其他函數(shù)中它是“不可見”的。2021/5/957大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸靜態(tài)局部變量使用在什么情況下需要用局部靜態(tài)變量呢？1.需要保留函數(shù)上一次調(diào)用結(jié)束時的值。例如可以用下例中的方法求ｎ！。如：intfac(intn){staticintf=1;//f為靜態(tài)局部變量，函數(shù)結(jié)束//時f的值不釋放//在f原值基礎(chǔ)上乘以nf=f*n;returnf;}2021/5/958大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸靜態(tài)局部變量使用2.如果初始化后，變量只被引用而不改變其值，則這時用靜態(tài)局部變量比較方便，以免每次調(diào)用時重新賦值。2021/5/959大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用extern聲明外部變量全局變量(外部變量)是在函數(shù)的外部定義的，它的作用域為從變量的定義處開始，到本程序文件的末尾。在此作用域內(nèi)，全局變量可以為本文件中各個函數(shù)所引用。編譯時將全局變量分配在靜態(tài)存儲區(qū)。有時需要用extern來聲明全局變量，以擴(kuò)展全局變量的作用域。2021/5/960大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸在一個文件內(nèi)聲明全局變量提前引用聲明大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部2021/5/961第九講——函數(shù)、遞推、遞歸在多文件程序中聲明外部變量外部變量聲明分析下例：file1.cppexternint a,b;intmain(){cout<<a<<″,″<<b<<endl;return 0;}注意：file2.cppint a=3,b=4;┆extern是用作變量聲明，而不是變量定義。它只是對一個已定義的外部變量作聲明，以擴(kuò)展其作用域。2021/5/962大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用extern擴(kuò)展全局變量的作用域，雖然能為程序設(shè)計帶來方便，但應(yīng)十分慎重，因為在執(zhí)行一個文件中的函數(shù)時，可能會改變了該全局變量的值，從而會影響到另一文件中的函數(shù)執(zhí)行結(jié)果。2021/5/963大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用static聲明靜態(tài)外部變量有時在程序設(shè)計中希望某些外部變量只限于被本文件引用，而不能被其他文件引用。這時可以在定義外部變量時加一個static聲明。例如：file1.cppstaticinta=3;intmain(){┆file2.cppexterninta;intfun(intn){┆a=a*n;┆}}2021/5/964大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸這種加上static聲明、只能用于本文件的外部變量（全局變量）稱為靜態(tài)外部變量。這就為程序的模塊化、通用性提供了方便。如果已知道其他文件不需要引用本文件的全局變量，可以對本文件中的全局變量都加上static，成為靜態(tài)外部變量，以免被其他文件誤用。需要指出，不要誤認(rèn)為用static聲明的外部變量才采用靜態(tài)存儲方式（存放在靜態(tài)存儲區(qū)中），而不加static的是動態(tài)存儲（存放在動態(tài)存儲區(qū)）。實際上，兩種形式的外部變量都用靜態(tài)存儲方式，只是作用范圍不同而已，都是在編譯時分配內(nèi)存的。2021/5/965大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸存儲期和作用域2021/5/966大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸變量的聲明和定義關(guān)于聲明和定義：針對函數(shù)而言，函數(shù)的聲明是函數(shù)的原型，而函數(shù)的定義是函數(shù)功能的建立；在聲明部分出現(xiàn)的變量有兩種情況：一種是需要建立存儲空間的（如inta）；另一種是不需要建立存儲空間的(externinta)；前者稱為定義性聲明，或簡稱定義；后者稱為引用性聲明；2021/5/967大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸為敘述方便，把建立存儲空間的聲明稱為定義；如:inta;而把不需要建立存儲空間的聲明稱為聲明；如：externinta;2021/5/968大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸外部變量定義和外部變量聲明的含義是不同的。外部變量的定義只能有一次，它的位置在所有函數(shù)之外，而同一文件中的外部變量的聲明可以有多次，它的位置可以在函數(shù)之內(nèi)，也可以在函數(shù)之外。系統(tǒng)根據(jù)外部變量的定義分配存儲單元。對外部變量的初始化只能在定義時進(jìn)行，而不能在聲明中進(jìn)行。所謂聲明，其作用是向編譯系統(tǒng)發(fā)出一個信息，聲明該變量是一個在后面定義的外部變量，僅僅是為了提前引用該變量而作的聲明。extern只用作聲明，而不用于定義。2021/5/969大連理工大學(xué)盤錦校區(qū)基礎(chǔ)教學(xué)部第九講——函數(shù)、遞推、遞歸用static來聲明一個變量的作用有二：(1)對局部變量用static聲明，使該變量在本函數(shù)調(diào)用結(jié)束后不釋放，整個程序執(zhí)行期間始終存在，使其存儲期為程序的全過程。(2)全局變量用static聲明，則該變量的作