搜索
《C++语言程序设计》第九讲函数、递推、递归第九讲——函数、递推、递归递推递推是计算机数值计算中的一个重要算法。大连理工大学盘锦校区基础教学部2思路：通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复运算的特点；递推法特点：从一个已知的事实出发，按一定规律推出下一个事实，再从这个新的已知事实出发，再向下推出一个新的事实。第九讲——函数、递推、递归递推举例（1）大连理工大学盘锦校区基础教学部3例:(猴子吃桃问题)猴子第1天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。问第1天猴子共摘了多少桃子？第九讲——函数、递推、递归解题思路：大连理工大学盘锦校区基础教学部4假设用S(i)表示第i天没吃之前的桃子数目；则S(1)即为第1天所摘的桃子数；S(10)=S(9)*1/2–1第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天没吃之前的桃子数第九讲——函数、递推、递归一般形式：S(i)=S(i-1)*1/2–1,大连理工大学盘锦校区基础教学部5i=2,3,…,10;这个公式可用于知第1天没吃之前的桃子数推算第2天没吃之前的，再推算第3天没吃之前的，…….。现在要求的是第1天没吃之前的。能否倒过来，先知第10天没吃之前的的再反推第9天没吃之的，……，直到第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第九讲——函数、递推、递归递推举例（2）大连理工大学盘锦校区基础教学部9递推数列一个数列从某一项起，它的任何一项都可以用它前面的若干项来确定，这样的数列称为递推数列，表示某项与其前面的若干项的关系就称为递推公式。例如自然数1,2，…,n的阶乘就可以形成如下数列：1！，2！，3！，…,(n-1)!,n!另fact(n)为n阶乘，依据后项与前项的关系可以写出递推公式：fact(n)=n*fact(n-1)(通项公式)fact(1)=1（边界条件）第九讲——函数、递推、递归递推算例（3）大连理工大学盘锦校区基础教学部10递推算法程序实现：有了通项公式和边界条件后，采用循环结构，从边界条件出发，利用通项公式通过若干步递推过程就可以求出结果；例：王小二自称刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切100刀最多能分成多少块？”第九讲——函数、递推、递归分析：切一刀大连理工大学盘锦校区基础教学部11切二刀切三刀切四刀令q(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(边界条件)第九讲——函数、递推、递归递推算例（3）参考程序：大连理工大学盘锦校区基础教学部13第九讲——函数、递推、递归递归递归算法在可计算理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言不涉及高深数学知识，只不过初学者建立起递归概念不太容易。看一个简单的例子：大连理工大学盘锦校区基础教学部14第九讲——函数、递推、递归递归有5个人坐在一起，问第5个人多少岁？他说比第4个人大两岁。问第4个人岁数，他说比第3个人大两岁。问第3个人，又说比第2个人大两岁。问第2个人，说比第1个人大两岁。最后问第1个人，他说是10岁。请问第5个人多大？解题思路：假设用age(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)=age(n-1)+2(n=1)(n2)大连理工大学盘锦校区基础教学部16第九讲——函数、递推、递归分析：上述求解是从求解目标出发，即将第n个人的年龄表示第(n-1)个人的年龄，再回溯到第（n-2）个人的年龄……直到第1个人的年龄；（回溯阶段）然后，采用递推方法，从第1个人的已知年龄推算第2个人的年龄，在推算第3个人的年龄，直到推算出第5个人的年龄；（递推阶段）这是一个递归问题，对它的求解可以分成回溯和递推两个阶段；显而易见，如果不希望递归过程无限制的进行下去，必须有一个结束递归过程的条件；如：age(1)=10大连理工大学盘锦校区基础教学部17第九讲——函数、递推、递归计算年龄函数：intage(intn)大连理工大学盘锦校区基础教学部18{intc;if(n==1){c=10;}else{c=age(n-1)+2;}returnc;}第九讲——函数、递推、递归递归调用大连理工大学盘锦校区基础教学部19在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归（recursive）调用;C++允许函数的递归调用；例：intf(intx){inty,z;z=f(y);return2*z;}第九讲——函数、递推、递归递归调用直接调用大连理工大学盘锦校区基础教学部20间接调用注意：上述两种情况都是无终止的自身调用；显然，程序中不应该出现这种无终止的调用，而只应出现有限次的，有终止的递归调用；可以用if语句控制，实现递归调用结束；第九讲——函数、递推、递归递归函数包含递归调用的函数，称为递归函数；计算年龄函数:intage(intn){intc;if(n==1){c=10;}else{c=age(n-1)+2;}returnc;}大连理工大学盘锦校区基础教学部21第九讲——函数、递推、递归递归函数大连理工大学盘锦校区基础教学部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第九讲——函数、递推、递归递归算例（2）大连理工大学盘锦校区基础教学部24用递归方法计算n!算法思路：若n=10,则n!=10*9!定义函数fact(n)表示计算n！的函数，则有fact(n)=n*fact(n-1),n1fact(n)=1,n=0,n=1;第九讲——函数、递推、递归递归算例（2）大连理工大学盘锦校区基础教学部25阶乘计算递归函数：iinnttffaacctt((iinnttnn)){{intc;if(cn==n=*0f||anct=(n=-11));c=1;reelstuernc;c=n*fact(n-1);returnc;}}结束递归条件第九讲——函数、递推、递归递归算例（3）大连理工大学盘锦校区基础教学部26用递归函数计算组合数：C(m,n)，即从m个数中取n个数的组合数；C(m,n)=C(m-1,n)+C(m-1,n-1);C(m,n)=0,m0,n0;C(m,n)=1,m==n;C(m,n)=m,n=1;第九讲——函数、递推、递归递归算例（3）大连理工大学盘锦校区基础教学部27第九讲——函数、递推、递归递归算例（4）大连理工大学盘锦校区基础教学部28例:(猴子吃桃问题)猴子第1天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半另加一个。到第10天早上想再吃时，就只剩下一个桃子了。问第1天猴子共摘了多少桃子？第九讲——函数、递推、递归解题思路：大连理工大学盘锦校区基础教学部29假设用S(i)表示第i天没吃之前的桃子数目；则S(1)即为第1天所摘的桃子数；S(10)=S(9)*1/2–1第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天没吃之前的桃子数第九讲——函数、递推、递归一般形式：S(i)=S(i-1)*1/2–1,大连理工大学盘锦校区基础教学部30i=2,3,…,10;这个公式可用于知第1天没吃之前的桃子数推算第2天没吃之前的，再推算第3天没吃之前的，…….。现在要求的是第1天没吃之前的。能否倒过来，先知第10天没吃之前的的再反推第9天没吃之的，……，直到第1天没吃之前的。为此将上式改写为：第九讲——函数、递推、递归一般形式：大连理工大学盘锦校区基础教学部31S(i-1)=2*(S(i)+1),i=2,3,4，…，10则S(1)即为第1天所摘的桃子数；S(1)=2*（S(2)+1）S(2)=2*（S(3)+1）…S(8)=2*（S(9)+1）S(10)=1第九讲——函数、递推、递归递归函数：intcount(intn)大连理工大学盘锦校区基础教学部32{intc;if(n==10)c=1;elsec=2*(count(n+1)+1);returnc;}这样可以吗？有没有问题？如果出现调用语句：count(11)?第九讲——函数、递推、递归递归函数：intcount(intn){intc;if(n10)return-1;if(n==10)c=1;elsec=2*(count(n+1)+1);returnc;}大连理工大学盘锦校区基础教学部33第九讲——函数、递推、递归递归方法大连理工大学盘锦校区基础教学部34递归实现：在时间和空间上的开销比较大；但符合人们的思路，程序容易理解；递归函数：只须写出递归公式和递归结束条件（即边界条件），即可很容易写出递归函数；第九讲——函数、递推、递归局部变量和全局变量大连理工大学盘锦校区基础教学部35一个程序可以包括若干个源程序文件（文件模块）；每个源程序文件又包括若干个函数；在每个函数中和函数外都可以定义变量。这些在不同地方定义的变量是否都在程序的全部范围内有效？如果不是，他们的有效范围是什么呢？第九讲——函数、递推、递归局部变量和全局变量大连理工大学盘锦校区基础教学部36局部变量在一个函数内部定义的变量是内部变量，它只在本函数范围内有效，换句话说只有在本函数内才能使用它们，在此函数之外是不能使用这些变量的。同样的，