资源描述：
《C++函数、递推、递归.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《C++语言程序设计》第九讲函数、递推、递归第九讲——函数、递推、递归递推递推是计算机数值计算中的一个重要算法。大连理工大学盘锦校区基础教学部2思路：通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复运算的特点；递推法特点：从一个已知的事实出发，按一定规律推出下一个事实，再从这个新的已知事实出发，再向下推出一个新的事实。第九讲——函数、递推、递归递推举例（1）大连理工大学盘锦校区基础教学部3例:(猴子吃桃问题)猴子第1天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半
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(
3、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,…
4、,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大连理工大学盘锦校区基础教学
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第九讲——函数、递推、递归递推举例（
6、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递推算法程序实现：有了通项公式和边界条件后，采用循
7、环结构，从边界条件出发，利用通项公式通过若干步递推过程就可以求出结果；例：王小二自称刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切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切二刀切三刀切四刀在切法上是让每两条线都有交点
8、。用归纳法可得出q(n)=q(n-1)+nq(0)=1(边界条件)第九讲——函数、递推、递归递推算例（3）参考程序：大连理工大学盘锦校区基础教学部13第九讲——函数、递推、递归递归递归算法在可计算理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有
