1、本网站免费注册后即可以下载，点击开通VIP会员可无限免费下载！
2、资料一般为word或PPT文档。建议使用IE9以上浏览器或360、谷歌、火狐浏览器浏览本站。
3、有任何下载问题，请联系微信客服。
扫描下方二维码，添加微信客服
选修1 算法与程序设计《第3章 常用算法及程序实现 第四节 递归法 活动 用递归法求解“兔子问题”》优秀ppt课件
上 海 科 技 教 育 出 版 社
一、引入概念
有4个人排成一队，问最后一个人的身高时，他说比第3个人高2厘米；问第3个人的身高时，他说比第2个人高2厘米；问第2个人的身高时,他说比第1个人高2厘米；最后问第1个人的身高,他说是170厘米。请问第4个人的身高是多少厘米？
1.实例说明
你身高多少厘米？
我比她高2厘米
我比他高2厘米
我比她高2厘米
我身高170厘米
你能算出我的身高吗？
要求第4个人的身高就必须先知道第3个人的身高，而第3个人的身高取决于第2个人的身高,第2个人的身高又取决于第1个人的身高,且每个人的身高都比前一个人要高2厘米,这类问题就是一个典型的递归问题。
2.问题分析
H(n) = H(n-1) + 2 n>1，
H(1) = 170 , n=1。
于是可得递归公式：
3.递归过程
⑵ . 递归问题由两部分组成：
一部分是可以直接处理的，也就是递归的终止条件即问题的初始条件，如H(1)=170；
另一部分是不可直接处理的,须将原问题转化为与原问题相似且更接近终止条件的新的问题。如H(n)=H(n-1)+2,原问题是H(n),新问题是H(n-1),显然H(n-1)更接近H(1)。
4.基本思想
⑴ . 递归过程可分为两个阶段：
递推阶段的工作是不断将原问题转化为另一个类似的新问题，直到某个新问题能根据已知条件计算出结果为止。例如图的左边斜下部分就是递推过程。
返回阶段是递推的逆过程，返回阶段是从递推结束处开始，一步一步向回推算结果，直到计算出原问题的结果为止。例如图的右边斜上部分就是返回过程。
二、基本活动: 用递归法求解“兔子问题”
一位农夫养了一对小兔子，他发现小兔子在出生后的第二个月就长成了大兔子，每对大兔子每月又可繁殖一对小兔子。如果一年内没有发生死亡的话，那么一年后这个农夫将有多少对兔子？