C++函数、递推、递归.ppt

-1-C+C+语言程序设计语言程序设计第九讲第九讲 函数、递推、递归函数、递推、递归第九讲第九讲函数、递推、递归函数、递推、递归递推递推递推递推是计算机数值计算中的一个重要算法。是计算机数值计算中的一个重要算法。大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部2思路：思路：通过数学推导，将复杂的运算化解为若干重复通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复运算的特点；的简单运算，以充分发挥计算机长于重复运算的特点；递递推推法法特特点点：从从一一个个已已知知的的事事实实出出发发，按按一一定定规规律律推推 出出下下一一个个事事实实，再再从从这这个个新新的的已已知知事事实实出出发发，再再向向下下 推出一个新的事实。推出一个新的事实。-3-第九讲第九讲函数、递推、递归函数、递推、递归递推举例（递推举例（1 1）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部3例例:(:(猴子吃桃问题猴子吃桃问题)猴子第猴子第1 1天摘下若干桃子，当即吃了一半，还不过瘾，天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第又多吃了一个。第2 2天早上又将剩下的桃子吃掉一半，天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一又多吃了一个。以后每天早上都吃了前一天剩下的一 半半另加一个。到第另加一个。到第1010天早上想再吃时，就只剩下一个天早上想再吃时，就只剩下一个 桃子桃子了。问第了。问第1 1天猴子共摘了多少桃子？天猴子共摘了多少桃子？-4-第九讲第九讲函数、递推、递归函数、递推、递归解题思路解题思路：大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部4假设用假设用 S(i)S(i)表示第表示第 i i 天没吃之前的桃子数目；天没吃之前的桃子数目；则则S(1)S(1)即为第即为第 1 1天所摘的桃子数；天所摘的桃子数；S(10)=S(9)*1/2 S(10)=S(9)*1/2 1 1 第第 10 10 天没吃之前的桃子数天没吃之前的桃子数S(2)=S(1)*1/2 1第 2 天没吃之前的桃子数S(3)=S(2)*1/2-1第 3 天没吃之前的桃子数S(9)=S(8)*1/2-1第 9 天没吃之前的桃子数-5-第九讲第九讲函数、递推、递归函数、递推、递归一般形式：一般形式：S(i)=S(i-1)*1/2 1,大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部5i=2,3,10;这个公式可用于知第这个公式可用于知第 1 1 天没吃之前的桃子数推算第天没吃之前的桃子数推算第 2 2 天天 没吃之前的，再推算第没吃之前的，再推算第 3 3天没吃之前的，天没吃之前的，.。现在要求的。现在要求的是是 第第 1 1 天没吃之前的。能否倒过来，先知天没吃之前的。能否倒过来，先知 第第 10 10 天没吃之天没吃之前的前的 的再反推第的再反推第 9 9天没吃之的，天没吃之的，直到第，直到第 1 1 天没吃之天没吃之前的。为前的。为 此将上式改写为：此将上式改写为：S(i-1)=2*(S(i)+1),i=10,9,8,2第九讲第九讲函数、递推、递归函数、递推、递归程序：程序：大连理工大学大连理工大学 盘锦校区基础教学部盘锦校区基础教学部 6第九讲第九讲函数、递推、递归函数、递推、递归分析：分析：一般形式：一般形式：S(i-1)=2*(S(i)+1),i=10,9,8,2;初始：初始：s2=1;/S(10)=1大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部7i=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)第九讲第九讲函数、递推、递归函数、递推、递归i=5大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部8s1=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=1-9-第九讲第九讲函数、递推、递归函数、递推、递归递推举例（递推举例（2 2）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部9递推数列递推数列 一个数列从某一项起，它的任何一项都可以用它前一个数列从某一项起，它的任何一项都可以用它前面的若干项面的若干项 来确定，这样的数列称为来确定，这样的数列称为递推数列递推数列，表示某项与，表示某项与其前面的若干其前面的若干 项的关系就称为项的关系就称为递推公式递推公式。例如自然数。例如自然数 1,21,2，,n 的阶乘就可的阶乘就可 以形成如下数列：以形成如下数列：1 1！，！，2 2！，！，3 3！，！，,(n-1)!,n!-1)!,n!另另fact(n)fact(n)为为 n n 阶乘，依据后项与前项的关系可以写出递推阶乘，依据后项与前项的关系可以写出递推公公式：式：fact(n)=n*fact(n-1)(fact(n)=n*fact(n-1)(通项公式通项公式)fact(1)=1fact(1)=1（边界条件）（边界条件）-10-第九讲第九讲函数、递推、递归函数、递推、递归递推算例（递推算例（3 3）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部10递推算法程序实现：递推算法程序实现：有了通项公式和边界条件后，采用循环有了通项公式和边界条件后，采用循环结构，从边界条件出结构，从边界条件出 发，利用通项公式通过若干步递推过发，利用通项公式通过若干步递推过程就可以求出结果；程就可以求出结果；例：例：王小二自称刀工不错，有人放一张大的煎饼在砧板上，问他：王小二自称刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切饼不许离开砧板，切 100 100 刀最多能分成多少块？刀最多能分成多少块？”第九讲第九讲函数、递推、递归函数、递推、递归分析：分析：切一刀切一刀大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部11切二刀切二刀切三刀切三刀切四刀切四刀令令 q(n)q(n)表示切表示切 n n 刀能分成的块数，由上图可知刀能分成的块数，由上图可知q(1)=1+1=2q(2)=1+1+2=4q(3)=1+1+2+3=7q(4)=1+1+2+3+4=11第九讲第九讲函数、递推、递归函数、递推、递归分析：分析：切一刀切一刀大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部12切二刀切二刀切三刀切三刀切四刀切四刀在切法上是让每两条线都有交点。用归纳法可得出在切法上是让每两条线都有交点。用归纳法可得出q(n)=q(n-1)+nq(0)=1(边界条件边界条件)-13-第九讲第九讲函数、递推、递归函数、递推、递归递推算例（递推算例（3 3）参考程序：参考程序：大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部13第九讲第九讲函数、递推、递归函数、递推、递归递归递归递归算法递归算法在可计算理论中占有重要地位，它是算法设计的有在可计算理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。力工具，对于拓展编程思路非常有用。就就递归算法递归算法而言不涉及高深数学知识，只不过初学者建立起递而言不涉及高深数学知识，只不过初学者建立起递 归概念不太容易。归概念不太容易。看一个简单的例子：看一个简单的例子：大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部14第九讲第九讲函数、递推、递归函数、递推、递归递归递归有有5 5 个人坐在一起，问第个人坐在一起，问第 5 5 个人多少岁？个人多少岁？他说比第他说比第 4 4个人个人大两岁。问第大两岁。问第4 4 个人岁数，他说比第个人岁数，他说比第 3 3 个人大两岁。问个人大两岁。问第第 3 3个人，又说比第个人，又说比第 2 2 个人大两岁。问第个人大两岁。问第 2 2个人，说比第个人，说比第 1 1个人个人大两岁。最后问第大两岁。最后问第 1 1个人，他说是个人，他说是 1010岁。请问第岁。请问第 5 5 个人多个人多大？大？解题思路：解题思路：假设用假设用 age(i)age(i)表示第表示第 i i个人的岁数，个人的岁数，则则大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部15借助循环结构采用递推方法求解！借助循环结构采用递推方法求解！age(5)=age(4)+2;age(4)age(3)=age(3)age(2)+2;2;age(2)=age(1)+2;age(1)=10;第九讲第九讲函数、递推、递归函数、递推、递归一般形式：一般形式：age(n)=10age(n)=10age(n)=age(age(n)=age(n n-1)+2-1)+2(n=1)(n=1)(n 2)(n 2)大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部16第九讲第九讲函数、递推、递归函数、递推、递归分析：分析：上上述述求求解解是是从从求求解解目目标标出出发发，即即将将第第 n n 个个人人的的年年龄龄表表示示第第 (n-1)(n-1)个个人人的的年年龄龄，再再回回溯溯到到第第 （n-2n-2）个个人人的的年年龄龄 直直 到第到第 1 1 个人的年龄；（个人的年龄；（回溯回溯阶段）阶段）然后，采用递推方法，从第然后，采用递推方法，从第 1 1 个人的已知年龄推算第个人的已知年龄推算第 2 2 个个人的年龄，在推算第人的年龄，在推算第 3 3个人的年龄，直到推算出第个人的年龄，直到推算出第 5 5个人的个人的 年龄；（年龄；（递推递推阶段）阶段）这这是是一一个个递递归归问问题题，对对它它的的求求解解可可以以分分成成 回回溯溯 和和 递递推推 两两 个个阶阶段段；显显而而易易见见，如如果果不不希希望望递递归归过过程程无无限限制制的的进进行行下下去去，必须必须有一个有一个结束递归过程结束递归过程的条件；如：的条件；如：age(1)=10age(1)=10大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部17-18-第九讲第九讲函数、递推、递归函数、递推、递归计算年龄函数：计算年龄函数：int age(int n)大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部18int c;if(n=1)c=10;else c=age(n-1)+2;return c;-19-第九讲第九讲函数、递推、递归函数、递推、递归递归调用递归调用大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部19在调用一个函数的过程中又出现直接或间接地调用该在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的函数本身，称为函数的递归（递归（recursiverecursive）调用）调用;C+C+允许函数的递归调用允许函数的递归调用；例：例：int f(int x)int y,z;z=f(y);return 2*z;-20-第九讲第九讲函数、递推、递归函数、递推、递归递归调用递归调用直接调用直接调用大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部20间接调用间接调用注意注意：上述两种情况都是：上述两种情况都是无终止无终止的自身调用；显然，的自身调用；显然，程序中不应该出现这种无终止的调用，而只应出现程序中不应该出现这种无终止的调用，而只应出现 有限次的，有终止的递归调用；有限次的，有终止的递归调用；可以用可以用if语句控制，语句控制，实现递归调用结束实现递归调用结束；-21-第九讲第九讲函数、递推、递归函数、递推、递归递归函数递归函数包含包含递归调用递归调用的函数，称为的函数，称为递归函数递归函数；计算年龄函数计算年龄函数:int age(int n)int c;if(n=1)c=10;else c=age(n-1)+2;returnreturn c;c;大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部21-22-第九讲第九讲函数、递推、递归函数、递推、递归递归函数递归函数大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部22计算年龄递归函数执行过程：计算年龄递归函数执行过程：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;-23-第九讲第九讲函数、递推、递归函数、递推、递归计算年龄程序计算年龄程序大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部23-24-第九讲第九讲函数、递推、递归函数、递推、递归递归算例（递归算例（2 2）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部24用递归方法计算用递归方法计算 n!n!算法思路：算法思路：若若 n=10,n=10,则则 n!=10*9!n!=10*9!定义函数定义函数 fact(n)fact(n)表示计算表示计算 n n！的函数，则有！的函数，则有fact(n)=n*fact(n-1),n 1fact(n)=1,n=0,n=1;-25-第九讲第九讲函数、递推、递归函数、递推、递归递归算例（递归算例（2 2）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部25阶乘计算递归函数：阶乘计算递归函数：iinntt ffaacctt(iinntt nn)int c;if(cn=n=*0 f|anct=(n=-11);c=1;reelstuern c;c=n*fact(n-1);return c;结束递归条件结束递归条件-26-第九讲第九讲函数、递推、递归函数、递推、递归递归算例（递归算例（3 3）大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部26用递归函数计算组合数：用递归函数计算组合数：C(m,n)C(m,n)，即从，即从 m m 个数中取个数中取 n n 个数的组合数；个数的组合数；C(m,n)=C(m-1,n)+C(m-1,n-1);C(m,n)=C(m-1,n)+C(m-1,n-1);C(m,n)=0,m 0,n 0;C(m,n)=0,m 0,n 10)return-1;if(n=10)c=1;elsec=2*(count(n+1)+1);return c;大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部33-34-第九讲第九讲函数、递推、递归函数、递推、递归递归方法递归方法大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部34递归实现：递归实现：在时间和空间上的开销比较大；但符合人们的思路，在时间和空间上的开销比较大；但符合人们的思路，程序容易理解；程序容易理解；递归函数：递归函数：只须写出只须写出递归公式递归公式和和递归结束条件递归结束条件（即边（即边 界条件），即可很容易写出递归函数；界条件），即可很容易写出递归函数；-35-第九讲第九讲函数、递推、递归函数、递推、递归局部变量和全局变量局部变量和全局变量大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部35一个一个程序程序可以包括若干个可以包括若干个源程序文件源程序文件（文件模块）；（文件模块）；每个源程序文件又包括若干个每个源程序文件又包括若干个函数函数；在每个函数中在每个函数中和函数外都可以定义和函数外都可以定义变量变量。这些在不同地方定义的变量是否都在程序的全部范围这些在不同地方定义的变量是否都在程序的全部范围 内有效？如果不是，他们的内有效？如果不是，他们的有效范围有效范围是什么呢？是什么呢？-36-第九讲第九讲函数、递推、递归函数、递推、递归局部变量和全局变量局部变量和全局变量大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部36局部变量局部变量在在一一个个函函数数内内部部定定义义的的变变量量是是内内部部变变量量，它它只只在在 本本函函数数范范围围内内有有效效，换换句句话话说说只只有有在在本本函函数数内内才才能能使使 用用它它们们，在在此此函函数数之之外外是是不不能能使使用用这这些些变变量量的的。同同样样 的的，在在复复合合语语句句中中定定义义的的变变量量只只在在复复合合语语句句内内范范围围内内 有效。有效。第九讲第九讲函数、递推、递归函数、递推、递归flflo oatat f1f1(intint a)a)/函数函数f1f1int b,c;int b,c;char f2(intchar f2(intint i,j;int i,j;int main()int main()int m,n;int m,n;int p,q;int p,q;b b、c c有效有效a a有效有效x,int y)x,int y)i i、j j有效有效/函数函数f2f2x x、y y有效有效/主函数主函数p p、q q在复合语句中有效在复合语句中有效m m、n n有效有效大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部37第九讲第九讲函数、递推、递归函数、递推、递归a a也只在也只在f1f1函数中有效。其他函数不能调用。函数中有效。其他函数不能调用。大连理工大学大连理工大学 盘锦校区基础教学部盘锦校区基础教学部38说明：说明：(1)(1)主函数主函数mainmain中定义的变量中定义的变量(m,n)(m,n)也只在主函数也只在主函数 中有效中有效,不会因为在主函数中定义而在整个文件或不会因为在主函数中定义而在整个文件或 程序中有效。主函数也不能使用其他函数中定义的程序中有效。主函数也不能使用其他函数中定义的 变量。变量。(2)(2)不同函数中可以使用同名的变量不同函数中可以使用同名的变量,它们代表不它们代表不 同的对象同的对象,互不干扰。例如互不干扰。例如,在在f1f1函数中定义了变量函数中定义了变量 b b和和c,c,倘若在倘若在f2f2函数中也定义变量函数中也定义变量b b和和c,c,它们在内存它们在内存 中占不同的单元中占不同的单元,不会混淆。不会混淆。(3)(3)可可以以在在一一个个函函数数内内的的复复合合语语句句中中定定义义变变量量,这这 些些变变量量只只在在本本复复合合语语句句中中有有效效,这这种种复复合合语语句句也也称称 为分程序或程序块。为分程序或程序块。(4)(4)形式参数也是局部变量。例如形式参数也是局部变量。例如f1f1函数中的形参函数中的形参-39-第九讲第九讲函数、递推、递归函数、递推、递归大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部39(5)(5)在在函函数数声声明明中中出出现现的的参参数数名名，其其作作用用范范围围只只在在本本 行行的的括括号号内内。实实际际上上，编编译译系系统统对对函函数数声声明明中中的的变变量量 名是忽略的，即使在调用函数时也没有为它们分配存名是忽略的，即使在调用函数时也没有为它们分配存储单元。储单元。例如例如int max(int a,int b);int max(int a,int b);int max(int x,intint max(int x,int y)y)coutxyendl;coutxyendl;coutabendl;coutabendl;/函数声明中出现函数声明中出现a a、b b/函数定义，形参是函数定义，形参是x x、y y/合法，合法，x x、y y在函数体中有效在函数体中有效/非法，非法，a a、b b在函数体中无效在函数体中无效编译时认为编译时认为maxmax函数体中的函数体中的a a和和b b未经定义。未经定义。-40-第九讲第九讲函数、递推、递归函数、递推、递归全局变量全局变量大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部40程序的编译单位是程序的编译单位是源程序文件（源程序文件（.cpp.cpp）,一个源文一个源文 件可以包含一个或若干个件可以包含一个或若干个函数函数。在函数内定义的变量是在函数内定义的变量是局部变量局部变量,而在函数之外定而在函数之外定 义的变量是外部变量，称为义的变量是外部变量，称为全局变量全局变量(global(global variable,variable,也称全程变量也称全程变量)。全局变量的有效范围为从定义变量的位置开始到全局变量的有效范围为从定义变量的位置开始到 本源文件结束。本源文件结束。如如第九讲第九讲函数、递推、递归函数、递推、递归int p=1,q=5;/int p=1,q=5;/全局变量全局变量float ffloat f/定义函数定义函数f1f11(a)1(a)int int a;a;围围全局变量全局变量c1c1、c2c2的作用范围的作用范围(int a)大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部41int b,c;char c1,c2;char f2(int x,int y)/定义函数f2int i,j;main()/主函数int m,n;-42-第九讲第九讲函数、递推、递归函数、递推、递归大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部42p p、q q、c1c1、c2c2都是全局变量，但它们的作用范围不都是全局变量，但它们的作用范围不 同，在同，在mainmain函数和函数和f2f2函数中可以使用全局变量函数中可以使用全局变量p p、q q、c1c1、c2c2，但在函数，但在函数f1f1中只能使用全局变量中只能使用全局变量p p、q q，而，而 不能使用不能使用c1c1和和c2c2。在一个函数中既可以使用本函数中的局部变量，又在一个函数中既可以使用本函数中的局部变量，又 可以使用有效的全局变量。可以使用有效的全局变量。说明：说明：(1)(1)设全局变量的作用是增加函数间数据联系的渠设全局变量的作用是增加函数间数据联系的渠 道。道。(2)(2)建议不在必要时不要使用全局变量，因为：建议不在必要时不要使用全局变量，因为：全局变量在程序的全局变量在程序的全部执行过程中全部执行过程中都占用存储单都占用存储单元，而不是仅在需要时才开辟单元。元，而不是仅在需要时才开辟单元。-43-第九讲第九讲函数、递推、递归函数、递推、递归大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部43 在程序设计中，在划分模块时要求模块的内聚在程序设计中，在划分模块时要求模块的内聚性强、与其他模块的耦合性弱。即性强、与其他模块的耦合性弱。即模块的功能要单模块的功能要单 一一（不要把许多互不相干的功能放到一个模块中），（不要把许多互不相干的功能放到一个模块中），与其他模块的相互影响要尽量少，而用全局变量是与其他模块的相互影响要尽量少，而用全局变量是 不符合这个原则的。不符合这个原则的。一一般般要要求求把把程程序序中中的的函函数数做做成成一一个个封封闭闭体体，除除 了了可可以以通通过过“实实参参形形参参”的的渠渠道道与与外外界界发发生生联联 系外，没有其他渠道。这样的程序移植性好，可读系外，没有其他渠道。这样的程序移植性好，可读性强。性强。-44-第九讲第九讲函数、递推、递归函数、递推、递归大连理工大学大连理工大学 盘锦校区基础教学部盘锦校区基础教学部 44 使用全局变量过多，会降低程序的清晰性。在各使用全局变量过多，会降低程序的清晰性。在各个函数执行时都可能改变全局变量的值，程序容易个函数执行时都可能改变全局变量的值，程序容易 出错。因此，要限制使用全局变量。出错。因此，要限制使用全局变量。(3)(3)如如果果在在同同一一个个源源文文件件中中，全全局局变变量量与与局局部部变变量量 同同名名，则则在在局局部部变变量量的的作作用用范范围围内内，全全局局变变量量被被屏屏 蔽，即它不起作用。蔽，即它不起作用。变量的有效范围称为变量的有效范围称为变量的作用域变量的作用域(scope)(scope)。归纳起。归纳起 来，变量有来，变量有4 4种不同的作用域种不同的作用域:文件作用域文件作用域(file(file scope)scope)、函数作用域函数作用域(function scope)(function scope)、块作用域块作用域 (block scope)(block scope)和和函数原型作用域函数原型作用域(function(functionprototype scope)prototype scope)。文件作用域是全局的，其他三。文件作用域是全局的，其他三者是局部的。者是局部的。-45-第九讲第九讲函数、递推、递归函数、递推、递归变量的存储类别变量的存储类别大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部45已介绍了变量的一种属性已介绍了变量的一种属性作用域作用域，作用域是从，作用域是从 空间的角度空间的角度来分析的，分为来分析的，分为全局变量全局变量和和局部变量局部变量。变量还有另一种属性变量还有另一种属性存储期存储期(storage storage durationduration，也称，也称生命期生命期)。存储期是指变量在内存中。存储期是指变量在内存中 的存在时间。这是从变量值存在的的存在时间。这是从变量值存在的时间角度时间角度来分析来分析 的。存储期可以分为静态存储期的。存储期可以分为静态存储期(static storage(static storage duration)duration)和动态存储期和动态存储期(dynamic storage(dynamic storage duration)duration)。这是由变量的。这是由变量的静态存储静态存储方式和方式和动态存储动态存储 方式决定的。方式决定的。-46-第九讲第九讲函数、递推、递归函数、递推、递归存储方式存储方式大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部46静态存储静态存储方式是指在程序运行期间，系统对变量分方式是指在程序运行期间，系统对变量分配固定的存储空间。配固定的存储空间。动态存储动态存储方式则是在程序运行期间，系统对变量动方式则是在程序运行期间，系统对变量动 态地分配存储空间。态地分配存储空间。-47-第九讲第九讲函数、递推、递归函数、递推、递归存储方式存储方式先看一下内存中的供用户使用的存储空间的情况。这先看一下内存中的供用户使用的存储空间的情况。这个存储空间可以分为三部分，即：个存储空间可以分为三部分，即：(1)(1)程序区程序区(2)(2)静态存储区静态存储区(3)(3)动态存储区动态存储区大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部47-48-第九讲第九讲函数、递推、递归函数、递推、递归静态存储区静态存储区大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部48数据分别存放在数据分别存放在静态静态存储区和存储区和动态动态存储区中。存储区中。全全局局变变量量全全部部存存放放在在静静态态存存储储区区中中，在在程程序序开开始始执执行行 时时给给全全局局变变量量分分配配存存储储单单元元，程程序序执执行行完完毕毕就就释释放放这这 些空间。些空间。在在程程序序执执行行过过程程中中它它们们占占据据固固定定的的存存储储单单元元，而而不不是是 动态地进行分配和释放。动态地进行分配和释放。-49-第九讲第九讲函数、递推、递归函数、递推、递归动态存储区动态存储区大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部49在动态存储区中存放以下数据：在动态存储区中存放以下数据：函数形式参数函数形式参数。在调用函数时给形参分配存储空间。在调用函数时给形参分配存储空间。函数中的自动变量函数中的自动变量（未加（未加staticstatic声明的局部变量，声明的局部变量，详见后面的介绍）。详见后面的介绍）。函数调用时的现场保护和返回地址函数调用时的现场保护和返回地址等。等。对以上这对以上这些数据，在些数据，在函数调用开始函数调用开始时分配动态存储空时分配动态存储空 间，函间，函数结束时释放这些空间。在程序执行过程中，数结束时释放这些空间。在程序执行过程中，这种分配和释放是动态的，如果在一个程序中这种分配和释放是动态的，如果在一个程序中两次两次调调用同一函数，则要进行用同一函数，则要进行两次分配和释放两次分配和释放，而两次分配，而两次分配给此函数中局部变量的存储空间地址可能是给此函数中局部变量的存储空间地址可能是不相同不相同的。的。-50-第九讲第九讲函数、递推、递归函数、递推、递归50大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部如果在一个程序中包含若干个函数，每个函数中的如果在一个程序中包含若干个函数，每个函数中的 局部变量的局部变量的存储期存储期并不等于整个程序的执行周期，它并不等于整个程序的执行周期，它 只是整个程序执行周期的一部分。根据函数调用的情只是整个程序执行周期的一部分。根据函数调用的情况，系统对局部变量动态地分配和释放存储空间。况，系统对局部变量动态地分配和释放存储空间。在在C+C+中变量除了有中变量除了有数据类型数据类型的属性之外，还有的属性之外，还有存存 储类别储类别(storage class)(storage class)的属性。存储类别指的是数的属性。存储类别指的是数 据在内存中存储的方法。存储方法分为据在内存中存储的方法。存储方法分为静态存储静态存储和和动动 态存储态存储两大类。具体包含两大类。具体包含4 4种：种：自动的自动的(auto)(auto)、静态的静态的 (static)(static)、寄存器寄存器的的(register)(register)和和外部的外部的(extern)(extern)。根据变量的根据变量的存储类别存储类别，可以知道变量的作用域和存储，可以知道变量的作用域和存储期。期。-51-第九讲第九讲函数、递推、递归函数、递推、递归自动变量自动变量大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部51函数中的局部变量，如果不用关键字函数中的局部变量，如果不用关键字staticstatic加以声加以声明，编译系统对它们是动态地分配存储空间的。明，编译系统对它们是动态地分配存储空间的。函数的形参函数的形参和和在函数中定义的变量在函数中定义的变量(包括在复合语包括在复合语 句中定义的变量句中定义的变量)都属此类。都属此类。在调用该函数时，系统给形参和函数中定义的变量在调用该函数时，系统给形参和函数中定义的变量 分配存储空间，数据存储在动态存储区中。在函数调分配存储空间，数据存储在动态存储区中。在函数调 用结束时就自动释放这些空间。如果是在复合语句中用结束时就自动释放这些空间。如果是在复合语句中 定义的变量，则在变量定义时分配存储空间，在复合定义的变量，则在变量定义时分配存储空间，在复合 语句结束时自动释放空间。因此这类语句结束时自动释放空间。因此这类局部变量局部变量称为自称为自 动变量动变量(auto variableauto variable)。-52-第九讲第九讲函数、递推、递归函数、递推、递归用用registerregister声明寄存器变量声明寄存器变量一般情况下，变量的值是存放在内存中的。当程序中用到哪一个变量的值时，由控制器发出指令将内存中中用到哪一个变量的值时，由控制器发出指令将内存中 该变量的值送到该变量的值送到CPUCPU中的运算器。经过运算器进行运算，中的运算器。经过运算器进行运算，如果需要存数，再从运算器将数据送到内存存放。如图如果需要存数，再从运算器将数据送到内存存放。如图 所示。所示。为提高执行效率，为提高执行效率，C+C+允许将允许将局部变量局部变量的的 放在放在CPUCPU中的中的寄存器寄存器中，需要用时直接从寄中，需要用时直接从寄 存器取出参加运算，不必再到内存中去存存器取出参加运算，不必再到内存中去存 取。这种变量叫做寄存器变量，用取。这种变量叫做寄存器变量，用关键字关键字registerregister作声明。作声明。但是，是建议性的；但是，是建议性的；值值大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部52-53-第九讲第九讲函数、递推、递归函数、递推、递归用用staticstatic声明静态局部变量声明静态局部变量大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部53有有时时希希望望函函数数中中的的局局部部变变量量的的值值在在函函数数调调用用结结束束后后不不 消消失失而而保保留留原原值值，即即其其占占用用的的存存储储单单元元不不释释放放，在在下下 一一次次该该函函数数调调用用时时，该该变变量量保保留留上上一一次次函函数数调调用用结结束束 时时的的值值。这这时时就就应应该该指指定定该该局局部部变变量量为为静静态态局局部部变变量量 (static local variablestatic local variable)。第九讲第九讲函数、递推、递归函数、递推、递归大连理工大学大连理工大学 盘锦校区基础教学盘锦校区基础教学部部54-55-第九讲第九讲函数、递推、递归函数、递推、递归先后先后3 3次调用次调用f f函数时，函数时，b b和和c c的值如书中表所示。的值如书中表所示。大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部55-56-第九讲第九讲函数、递推、递归函数、递推、递归静态局部变量说明静态局部变量说明(1)(1)静静态态局局部部变变量量在在静静态态存存储储区区内内分分配配存存储储单单元元。在在程程序序整整个个运运行行期期间间都都不不释释放放。而而自自动动变变量量（即即动动 态态局局部部变变量量）属属于于动动态态存存储储类类别别，存存储储在在动动态态存存储储 区区空空间间(而而不不是是静静态态存存储储区区空空间间)，函函数数调调用用结结束束后后 即释放。即释放。(2)(2)为为静态局部变量静态局部变量赋初值是在赋初值是在编译时编译时进行值的，进行值的，即即只赋初值只赋初值一次，在程序运行时它已有初值。以后一次，在程序运行时它已有初值。以后 每次每次调用函数时不再重新赋初值而只是保留上次函调用函数时不再重新赋初值而只是保留上次函 数调用数调用结束时的值。而为结束时的值。而为自动变量赋初值自动变量赋初值，不是在不是在 编译时进编译时进行的，而是在函数调用时进行行的，而是在函数调用时进行，每调用一，每调用一 次函数重新次函数重新给一次初值给一次初值大连大连，理工理工相相大学大学当当盘锦校盘锦校于于区基区基执执础教础教行行学部学部一次赋值语句。一次赋值语句。56-57-第九讲第九讲函数、递推、递归函数、递推、递归(3)(3)如果在定义局部变量时不赋初值的话，对如果在定义局部变量时不赋初值的话，对静态静态 局部变量局部变量来说，编译时自动赋初值来说，编译时自动赋初值0(0(对数值型变量对数值型变量)或空字符或空字符(对字符型变量对字符型变量)。而对。而对自动变量自动变量来说，如来说，如 果不赋初值，则它的值是一个果不赋初值，则它的值是一个不确定的值不确定的值。这是由。这是由 于每次函数调用结束后存储单元已释放，下次调用于每次函数调用结束后存储单元已释放，下次调用时又重新另分配存储单元，而时又重新另分配存储单元，而所分配的单元中的值所分配的单元中的值 是不确定的是不确定的。大连理工大学大连理工大学 盘锦校盘锦校区基础教学部区基础教学部57(4)(4)虽然虽然静态局部变量静态局部变量在函数调用结束后仍然存在，在函数调用结束后仍然存在，但其他函数是不能引用它的，也就是说，在其他函但其他函数是不能引用它的，也就是说，在其他函数中它是数中它是“不