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

C+語(yǔ)言程序設(shè)計(jì),第九講函數(shù)、遞推、遞歸,第九講函數(shù)、遞推、遞歸遞推遞推是計(jì)算機(jī)數(shù)值計(jì)算中的一個(gè)重要算法。,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,2,思路：通過(guò)數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡(jiǎn)單運(yùn)算，以充分發(fā)揮計(jì)算機(jī)長(zhǎng)于重復(fù)運(yùn)算的特點(diǎn)；遞推法特點(diǎn)：從一個(gè)已知的事實(shí)出發(fā)，按一定規(guī)律推出下一個(gè)事實(shí)，再?gòu)倪@個(gè)新的已知事實(shí)出發(fā)，再向下推出一個(gè)新的事實(shí)。,第九講函數(shù)、遞推、遞歸,遞推舉例（1）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,3,例:(猴子吃桃問(wèn)題)猴子第1天摘下若干桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了一個(gè)。第2天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半另加一個(gè)。到第10天早上想再吃時(shí)，就只剩下一個(gè)桃子了。問(wèn)第1天猴子共摘了多少桃子？,第九講函數(shù)、遞推、遞歸,解題思路：,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,4,假設(shè)用S(i)表示第i天沒(méi)吃之前的桃子數(shù)目；則S(1)即為第1天所摘的桃子數(shù)；,S(10)=S(9)*1/21第10天沒(méi)吃之前的桃子數(shù),第九講函數(shù)、遞推、遞歸,一般形式：S(i)=S(i-1)*1/21,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,5,i=2,3,10;這個(gè)公式可用于知第1天沒(méi)吃之前的桃子數(shù)推算第2天沒(méi)吃之前的，再推算第3天沒(méi)吃之前的，.?，F(xiàn)在要求的是第1天沒(méi)吃之前的。能否倒過(guò)來(lái)，先知第10天沒(méi)吃之前的的再反推第9天沒(méi)吃之的，直到第1天沒(méi)吃之前的。為此將上式改寫(xiě)為：S(i-1)=2*(S(i)+1),i=10,9,8,2,第九講函數(shù)、遞推、遞歸,程序：,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部6,第九講函數(shù)、遞推、遞歸分析：一般形式：S(i-1)=2*(S(i)+1),i=10,9,8,2;初始：s2=1;/S(10)=1,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,7,i=9,s1=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=8,i=7,i=6,s1=2*(s2+1);s2=s1;,/S(6)=2*(S(7)+1)/s2=s1=S(6),第九講函數(shù)、遞推、遞歸,i=5,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,8,s1=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=4,s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;s1=2*(s2+1);s2=s1;,i=3,i=2,i=1,第九講函數(shù)、遞推、遞歸,遞推舉例（2）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,9,遞推數(shù)列一個(gè)數(shù)列從某一項(xiàng)起，它的任何一項(xiàng)都可以用它前面的若干項(xiàng)來(lái)確定，這樣的數(shù)列稱(chēng)為遞推數(shù)列，表示某項(xiàng)與其前面的若干項(xiàng)的關(guān)系就稱(chēng)為遞推公式。例如自然數(shù)1,2，,n的階乘就可以形成如下數(shù)列：1！，2！，3！，,(n-1)!,n!另fact(n)為n階乘，依據(jù)后項(xiàng)與前項(xiàng)的關(guān)系可以寫(xiě)出遞推公式：fact(n)=n*fact(n-1)(通項(xiàng)公式)fact(1)=1（邊界條件）,第九講函數(shù)、遞推、遞歸,遞推算例（3）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,10,遞推算法程序?qū)崿F(xiàn)：有了通項(xiàng)公式和邊界條件后，采用循環(huán)結(jié)構(gòu)，從邊界條件出發(fā)，利用通項(xiàng)公式通過(guò)若干步遞推過(guò)程就可以求出結(jié)果；例：王小二自稱(chēng)刀工不錯(cuò)，有人放一張大的煎餅在砧板上，問(wèn)他：“餅不許離開(kāi)砧板，切100刀最多能分成多少塊？”,第九講函數(shù)、遞推、遞歸,分析：,切一刀,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,11,切二刀,切三刀切四刀,令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=11,第九講函數(shù)、遞推、遞歸,分析：,切一刀,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,12,切二刀,切三刀切四刀,在切法上是讓每?jī)蓷l線(xiàn)都有交點(diǎn)。用歸納法可得出q(n)=q(n-1)+nq(0)=1(邊界條件),第九講函數(shù)、遞推、遞歸,遞推算例（3,）,參考程序：,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,13,第九講函數(shù)、遞推、遞歸遞歸遞歸算法在可計(jì)算理論中占有重要地位，它是算法設(shè)計(jì)的有力工具，對(duì)于拓展編程思路非常有用。就遞歸算法而言不涉及高深數(shù)學(xué)知識(shí)，只不過(guò)初學(xué)者建立起遞歸概念不太容易。看一個(gè)簡(jiǎn)單的例子：,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,14,第九講函數(shù)、遞推、遞歸遞歸有5個(gè)人坐在一起，問(wèn)第5個(gè)人多少歲？他說(shuō)比第4個(gè)人大兩歲。問(wèn)第4個(gè)人歲數(shù)，他說(shuō)比第3個(gè)人大兩歲。問(wèn)第3個(gè)人，又說(shuō)比第2個(gè)人大兩歲。問(wèn)第2個(gè)人，說(shuō)比第1個(gè)人大兩歲。最后問(wèn)第1個(gè)人，他說(shuō)是10歲。請(qǐng)問(wèn)第5個(gè)人多大？解題思路：假設(shè)用age(i)表示第i個(gè)人的歲數(shù)，則,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,15,借助循環(huán)結(jié)構(gòu)采用遞推方法求解！,第九講函數(shù)、遞推、遞歸,一般形式：,age(n)=10age(n)=age(n-1)+2,(n=1)(n2),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,16,第九講函數(shù)、遞推、遞歸,分析：上述求解是從求解目標(biāo)出發(fā)，即將第n個(gè)人的年齡表示第(n-1)個(gè)人的年齡，再回溯到第（n-2）個(gè)人的年齡直到第1個(gè)人的年齡；（回溯階段）然后，采用遞推方法，從第1個(gè)人的已知年齡推算第2個(gè)人的年齡，在推算第3個(gè)人的年齡，直到推算出第5個(gè)人的年齡；（遞推階段）這是一個(gè)遞歸問(wèn)題，對(duì)它的求解可以分成回溯和遞推兩個(gè)階段；顯而易見(jiàn)，如果不希望遞歸過(guò)程無(wú)限制的進(jìn)行下去，必須有一個(gè)結(jié)束遞歸過(guò)程的條件；如：age(1)=10,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,17,第九講函數(shù)、遞推、遞歸,計(jì)算年齡函數(shù)：intage(intn),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,18,intc;if(n=1)c=10;elsec=age(n-1)+2;returnc;,第九講函數(shù)、遞推、遞歸,遞歸調(diào)用,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,19,在調(diào)用一個(gè)函數(shù)的過(guò)程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，稱(chēng)為函數(shù)的遞歸（recursive）調(diào)用;C+允許函數(shù)的遞歸調(diào)用；例：intf(intx)inty,z;z=f(y);return2*z;,第九講函數(shù)、遞推、遞歸,遞歸調(diào)用,直接調(diào)用,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,20,間接調(diào)用,注意：上述兩種情況都是無(wú)終止的自身調(diào)用；顯然，程序中不應(yīng)該出現(xiàn)這種無(wú)終止的調(diào)用，而只應(yīng)出現(xiàn)有限次的，有終止的遞歸調(diào)用；可以用if語(yǔ)句控制，實(shí)現(xiàn)遞歸調(diào)用結(jié)束；,第九講函數(shù)、遞推、遞歸,遞歸函數(shù),包含遞歸調(diào)用的函數(shù)，稱(chēng)為遞歸函數(shù)；計(jì)算年齡函數(shù):intage(intn)intc;,if(n=1)c=10;,elsec=age(n-1)+2;returnc;,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,21,第九講函數(shù)、遞推、遞歸,遞歸函數(shù),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,22,計(jì)算年齡遞歸函數(shù)執(zhí)行過(guò)程：,第九講函數(shù)、遞推、遞歸,計(jì)算年齡程序,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,23,第九講函數(shù)、遞推、遞歸,遞歸算例（2）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,24,用遞歸方法計(jì)算n!算法思路：若n=10,則n!=10*9!定義函數(shù)fact(n)表示計(jì)算n！的函數(shù)，則有,第九講函數(shù)、遞推、遞歸,遞歸算例（2）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,25,階乘計(jì)算遞歸函數(shù)：iinnttffaacctt(iinnttnn)intc;if(cn=n=*0f|anct=(n=-11);c=1;reelstuernc;,c=n*fact(n-1);returnc;,結(jié)束遞歸條件,第九講函數(shù)、遞推、遞歸,遞歸算例（3）,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,26,用遞歸函數(shù)計(jì)算組合數(shù)：C(m,n)，即從m個(gè)數(shù)中取n個(gè)數(shù)的組合數(shù)；C(m,n)=C(m-1,n)+C(m-1,n-1);C(m,n)=0,m0,n10)return-1;if(n=10)c=1;elsec=2*(count(n+1)+1);returnc;,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,33,第九講函數(shù)、遞推、遞歸,遞歸方法,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,34,遞歸實(shí)現(xiàn)：在時(shí)間和空間上的開(kāi)銷(xiāo)比較大；但符合人們的思路，程序容易理解；遞歸函數(shù)：只須寫(xiě)出遞歸公式和遞歸結(jié)束條件（即邊界條件），即可很容易寫(xiě)出遞歸函數(shù)；,第九講函數(shù)、遞推、遞歸,局部變量和全局變量,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,35,一個(gè)程序可以包括若干個(gè)源程序文件（文件模塊）；每個(gè)源程序文件又包括若干個(gè)函數(shù)；在每個(gè)函數(shù)中和函數(shù)外都可以定義變量。這些在不同地方定義的變量是否都在程序的全部范圍內(nèi)有效？如果不是，他們的有效范圍是什么呢？,第九講函數(shù)、遞推、遞歸,局部變量和全局變量,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,36,局部變量在一個(gè)函數(shù)內(nèi)部定義的變量是內(nèi)部變量，它只在本函數(shù)范圍內(nèi)有效，換句話(huà)說(shuō)只有在本函數(shù)內(nèi)才能使用它們，在此函數(shù)之外是不能使用這些變量的。同樣的，在復(fù)合語(yǔ)句中定義的變量只在復(fù)合語(yǔ)句內(nèi)范圍內(nèi)有效。,第九講函數(shù)、遞推、遞歸,floatf1(inta),/函數(shù)f1,intb,c;charf2(intinti,j;intmain()intm,n;intp,q;,b、c有效,a有效,x,inty)i、j有效,/函數(shù)f2,x、y有效,/主函數(shù),p、q在復(fù)合語(yǔ)句中有效,m、n有效,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,37,第九講函數(shù)、遞推、遞歸,a也只在f1函數(shù)中有效。其他函數(shù)不能調(diào)用。大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,38,說(shuō)明：,(1)主函數(shù)main中定義的變量(m,n)也只在主函數(shù)中有效,不會(huì)因?yàn)樵谥骱瘮?shù)中定義而在整個(gè)文件或程序中有效。主函數(shù)也不能使用其他函數(shù)中定義的變量。(2)不同函數(shù)中可以使用同名的變量,它們代表不同的對(duì)象,互不干擾。例如,在f1函數(shù)中定義了變量b和c,倘若在f2函數(shù)中也定義變量b和c,它們?cè)趦?nèi)存中占不同的單元,不會(huì)混淆。(3)可以在一個(gè)函數(shù)內(nèi)的復(fù)合語(yǔ)句中定義變量,這些變量只在本復(fù)合語(yǔ)句中有效,這種復(fù)合語(yǔ)句也稱(chēng)為分程序或程序塊。(4)形式參數(shù)也是局部變量。例如f1函數(shù)中的形參,第九講函數(shù)、遞推、遞歸,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,39,(5)在函數(shù)聲明中出現(xiàn)的參數(shù)名，其作用范圍只在本行的括號(hào)內(nèi)。實(shí)際上，編譯系統(tǒng)對(duì)函數(shù)聲明中的變量名是忽略的，即使在調(diào)用函數(shù)時(shí)也沒(méi)有為它們分配存,儲(chǔ)單元。例如,intmax(inta,intb);intmax(intx,inty)coutxyendl;coutabendl;,/函數(shù)聲明中出現(xiàn)a、b,/函數(shù)定義，形參是x、y/合法，x、y在函數(shù)體中有效/非法，a、b在函數(shù)體中無(wú)效,編譯時(shí)認(rèn)為max函數(shù)體中的a和b未經(jīng)定義。,第九講函數(shù)、遞推、遞歸,全局變量,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,40,程序的編譯單位是源程序文件（.cpp）,一個(gè)源文件可以包含一個(gè)或若干個(gè)函數(shù)。在函數(shù)內(nèi)定義的變量是局部變量,而在函數(shù)之外定義的變量是外部變量，稱(chēng)為全局變量(globalvariable,也稱(chēng)全程變量)。全局變量的有效范圍為從定義變量的位置開(kāi)始到本源文件結(jié)束。如,第九講函數(shù)、遞推、遞歸,intp=1,q=5;/全局變量,floatf/定義函數(shù)f1,1(a),inta;,圍,全局變量c1、c2的作用范圍,(inta),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,41,第九講函數(shù)、遞推、遞歸,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,42,p、q、c1、c2都是全局變量，但它們的作用范圍不同，在main函數(shù)和f2函數(shù)中可以使用全局變量p、q、c1、c2，但在函數(shù)f1中只能使用全局變量p、q，而不能使用c1和c2。,在一個(gè)函數(shù)中既可以使用本函數(shù)中的局部變量，又可以使用有效的全局變量。說(shuō)明：(1)設(shè)全局變量的作用是增加函數(shù)間數(shù)據(jù)聯(lián)系的渠道。(2)建議不在必要時(shí)不要使用全局變量，因?yàn)椋喝肿兞吭诔绦虻娜繄?zhí)行過(guò)程中都占用存儲(chǔ)單元，而不是僅在需要時(shí)才開(kāi)辟單元。,第九講函數(shù)、遞推、遞歸,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,43,在程序設(shè)計(jì)中，在劃分模塊時(shí)要求模塊的內(nèi)聚,性強(qiáng)、與其他模塊的耦合性弱。即模塊的功能要單一（不要把許多互不相干的功能放到一個(gè)模塊中），與其他模塊的相互影響要盡量少，而用全局變量是不符合這個(gè)原則的。一般要求把程序中的函數(shù)做成一個(gè)封閉體，除了可以通過(guò)“實(shí)參形參”的渠道與外界發(fā)生聯(lián)系外，沒(méi)有其他渠道。這樣的程序移植性好，可讀性強(qiáng)。,第九講函數(shù)、遞推、遞歸,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部44,使用全局變量過(guò)多，會(huì)降低程序的清晰性。在各個(gè)函數(shù)執(zhí)行時(shí)都可能改變?nèi)肿兞康闹?，程序容易出錯(cuò)。因此，要限制使用全局變量。,(3)如果在同一個(gè)源文件中，全局變量與局部變量同名，則在局部變量的作用范圍內(nèi)，全局變量被屏蔽，即它不起作用。變量的有效范圍稱(chēng)為變量的作用域(scope)。歸納起來(lái)，變量有4種不同的作用域:文件作用域(filescope)、函數(shù)作用域(functionscope)、塊作用域(blockscope)和函數(shù)原型作用域(functionprototypescope)。文件作用域是全局的，其他三,者是局部的。,第九講函數(shù)、遞推、遞歸,變量的存儲(chǔ)類(lèi)別,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,45,已介紹了變量的一種屬性作用域，作用域是從空間的角度來(lái)分析的，分為全局變量和局部變量。變量還有另一種屬性存儲(chǔ)期(storageduration，也稱(chēng)生命期)。存儲(chǔ)期是指變量在內(nèi)存中的存在時(shí)間。這是從變量值存在的時(shí)間角度來(lái)分析的。存儲(chǔ)期可以分為靜態(tài)存儲(chǔ)期(staticstorageduration)和動(dòng)態(tài)存儲(chǔ)期(dynamicstorageduration)。這是由變量的靜態(tài)存儲(chǔ)方式和動(dòng)態(tài)存儲(chǔ)方式?jīng)Q定的。,第九講函數(shù)、遞推、遞歸,存儲(chǔ)方式,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,46,靜態(tài)存儲(chǔ)方式是指在程序運(yùn)行期間，系統(tǒng)對(duì)變量分配固定的存儲(chǔ)空間。動(dòng)態(tài)存儲(chǔ)方式則是在程序運(yùn)行期間，系統(tǒng)對(duì)變量動(dòng)態(tài)地分配存儲(chǔ)空間。,第九講函數(shù)、遞推、遞歸,存儲(chǔ)方式,先看一下內(nèi)存中的供用戶(hù)使用的存儲(chǔ)空間的情況。這個(gè)存儲(chǔ)空間可以分為三部分，即：(1)程序區(qū)(2)靜態(tài)存儲(chǔ)區(qū)(3)動(dòng)態(tài)存儲(chǔ)區(qū),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,47,第九講函數(shù)、遞推、遞歸,靜態(tài)存儲(chǔ)區(qū),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,48,數(shù)據(jù)分別存放在靜態(tài)存儲(chǔ)區(qū)和動(dòng)態(tài)存儲(chǔ)區(qū)中。全局變量全部存放在靜態(tài)存儲(chǔ)區(qū)中，在程序開(kāi)始執(zhí)行時(shí)給全局變量分配存儲(chǔ)單元，程序執(zhí)行完畢就釋放這些空間。在程序執(zhí)行過(guò)程中它們占據(jù)固定的存儲(chǔ)單元，而不是動(dòng)態(tài)地進(jìn)行分配和釋放。,第九講函數(shù)、遞推、遞歸,動(dòng)態(tài)存儲(chǔ)區(qū),大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,49,在動(dòng)態(tài)存儲(chǔ)區(qū)中存放以下數(shù)據(jù)：函數(shù)形式參數(shù)。在調(diào)用函數(shù)時(shí)給形參分配存儲(chǔ)空間。函數(shù)中的自動(dòng)變量（未加static聲明的局部變量，詳見(jiàn)后面的介紹）。函數(shù)調(diào)用時(shí)的現(xiàn)場(chǎng)保護(hù)和返回地址等。對(duì)以上這些數(shù)據(jù)，在函數(shù)調(diào)用開(kāi)始時(shí)分配動(dòng)態(tài)存儲(chǔ)空間，函數(shù)結(jié)束時(shí)釋放這些空間。在程序執(zhí)行過(guò)程中，這種分配和釋放是動(dòng)態(tài)的，如果在一個(gè)程序中兩次調(diào)用同一函數(shù)，則要進(jìn)行兩次分配和釋放，而兩次分配給此函數(shù)中局部變量的存儲(chǔ)空間地址可能是不相同的。,第九講函數(shù)、遞推、遞歸,50,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,如果在一個(gè)程序中包含若干個(gè)函數(shù)，每個(gè)函數(shù)中的局部變量的存儲(chǔ)期并不等于整個(gè)程序的執(zhí)行周期，它只是整個(gè)程序執(zhí)行周期的一部分。根據(jù)函數(shù)調(diào)用的情況，系統(tǒng)對(duì)局部變量動(dòng)態(tài)地分配和釋放存儲(chǔ)空間。,在C+中變量除了有數(shù)據(jù)類(lèi)型的屬性之外，還有存儲(chǔ)類(lèi)別(storageclass)的屬性。存儲(chǔ)類(lèi)別指的是數(shù)據(jù)在內(nèi)存中存儲(chǔ)的方法。存儲(chǔ)方法分為靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)兩大類(lèi)。具體包含4種：自動(dòng)的(auto)、靜態(tài)的(static)、寄存器的(register)和外部的(extern)。根據(jù)變量的存儲(chǔ)類(lèi)別，可以知道變量的作用域和存儲(chǔ),期。,第九講函數(shù)、遞推、遞歸,自動(dòng)變量,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,51,函數(shù)中的局部變量，如果不用關(guān)鍵字static加以聲明，編譯系統(tǒng)對(duì)它們是動(dòng)態(tài)地分配存儲(chǔ)空間的。函數(shù)的形參和在函數(shù)中定義的變量(包括在復(fù)合語(yǔ)句中定義的變量)都屬此類(lèi)。在調(diào)用該函數(shù)時(shí)，系統(tǒng)給形參和函數(shù)中定義的變量分配存儲(chǔ)空間，數(shù)據(jù)存儲(chǔ)在動(dòng)態(tài)存儲(chǔ)區(qū)中。在函數(shù)調(diào)用結(jié)束時(shí)就自動(dòng)釋放這些空間。如果是在復(fù)合語(yǔ)句中定義的變量，則在變量定義時(shí)分配存儲(chǔ)空間，在復(fù)合語(yǔ)句結(jié)束時(shí)自動(dòng)釋放空間。因此這類(lèi)局部變量稱(chēng)為自動(dòng)變量(autovariable)。,第九講函數(shù)、遞推、遞歸,用register聲明寄存器變量一般情況下，變量的值是存放在內(nèi)存中的。當(dāng)程序,中用到哪一個(gè)變量的值時(shí)，由控制器發(fā)出指令將內(nèi)存中該變量的值送到CPU中的運(yùn)算器。經(jīng)過(guò)運(yùn)算器進(jìn)行運(yùn)算，如果需要存數(shù)，再?gòu)倪\(yùn)算器將數(shù)據(jù)送到內(nèi)存存放。如圖所示。為提高執(zhí)行效率，C+允許將局部變量的放在CPU中的寄存器中，需要用時(shí)直接從寄存器取出參加運(yùn)算，不必再到內(nèi)存中去存取。這種變量叫做寄存器變量，用關(guān)鍵字register作聲明。但是，是建議性的；,值,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,52,第九講函數(shù)、遞推、遞歸,用static聲明靜態(tài)局部變量,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,53,有時(shí)希望函數(shù)中的局部變量的值在函數(shù)調(diào)用結(jié)束后不消失而保留原值，即其占用的存儲(chǔ)單元不釋放，在下一次該函數(shù)調(diào)用時(shí)，該變量保留上一次函數(shù)調(diào)用結(jié)束時(shí)的值。這時(shí)就應(yīng)該指定該局部變量為靜態(tài)局部變量(staticlocalvariable)。,第九講函數(shù)、遞推、遞歸,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,54,第九講函數(shù)、遞推、遞歸,先后3次調(diào)用f函數(shù)時(shí)，b和c的值如書(shū)中表所示。,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,55,第九講函數(shù)、遞推、遞歸,靜態(tài)局部變量說(shuō)明,(1)靜態(tài)局部變量在靜態(tài)存儲(chǔ)區(qū)內(nèi)分配存儲(chǔ)單元。在程序整個(gè)運(yùn)行期間都不釋放。而自動(dòng)變量（即動(dòng)態(tài)局部變量）屬于動(dòng)態(tài)存儲(chǔ)類(lèi)別，存儲(chǔ)在動(dòng)態(tài)存儲(chǔ)區(qū)空間(而不是靜態(tài)存儲(chǔ)區(qū)空間)，函數(shù)調(diào)用結(jié)束后即釋放。(2)為靜態(tài)局部變量賦初值是在編譯時(shí)進(jìn)行值的，即只賦初值一次，在程序運(yùn)行時(shí)它已有初值。以后每次調(diào)用函數(shù)時(shí)不再重新賦初值而只是保留上次函數(shù)調(diào)用結(jié)束時(shí)的值。而為自動(dòng)變量賦初值，不是在編譯時(shí)進(jìn)行的，而是在函數(shù)調(diào)用時(shí)進(jìn)行，每調(diào)用一次函數(shù)重新給一次初值大連，理工相大學(xué)當(dāng)盤(pán)錦校于區(qū)基執(zhí)礎(chǔ)教行學(xué)部一次賦值語(yǔ)句。56,第九講函數(shù)、遞推、遞歸,(3)如果在定義局部變量時(shí)不賦初值的話(huà)，對(duì)靜態(tài)局部變量來(lái)說(shuō)，編譯時(shí)自動(dòng)賦初值0(對(duì)數(shù)值型變量)或空字符(對(duì)字符型變量)。而對(duì)自動(dòng)變量來(lái)說(shuō)，如果不賦初值，則它的值是一個(gè)不確定的值。這是由于每次函數(shù)調(diào)用結(jié)束后存儲(chǔ)單元已釋放，下次調(diào)用時(shí)又重新另分配存儲(chǔ)單元，而所分配的單元中的值是不確定的。,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,57,(4)雖然靜態(tài)局部變量在函數(shù)調(diào)用結(jié)束后仍然存在，但其他函數(shù)是不能引用它的，也就是說(shuō)，在其他函數(shù)中它是“不可見(jiàn)”的。,第九講函數(shù)、遞推、遞歸,靜態(tài)局部變量使用,大連理工大學(xué)盤(pán)錦校區(qū)基礎(chǔ)教學(xué)部,58,在什么情況下需要用局部靜態(tài)變量呢？1.需要保留函數(shù)上一次調(diào)用結(jié)束時(shí)的值。例如可以用下例中的方法求！。如：intfac(intn),statici