5.2.2 递归-教学设计（表格式）

教学设计 课程基本信息 课题 5.2 迭 代 与 递 归 （二）递 归 教学目标 1. 通过小猴摘桃子启发理解递归的算法思想。 2. 引导能合理选用数据结构，理清递归公式及结束条件，递归的递推与回归两个阶段。 3. 通过实例的形式用自然语言、流程图、Python语言描述递归算法。 4. 引导学生掌握递归算法的一般设计思路。 5. 引导学生自觉应用递归算法，解决生活、学习中的问题。 教学内容 教学重点： 1. 递归公式及结束条件，递归的递推与回归两个阶段。 2. 自觉应用递归算法，解决生活、学习中的问题。 教学难点： 自觉应用递归算法，解决生活、学习中的问题。 教学过程 一、认识本节课的学习目标，自学教材内容。 二、情境导入：猜猜E娃娃有几个铜币？ 三、递归算法基本思想： 通过函数自己调用自己来实现，也就是在其定义中直接或间接调用自身的方法，称之为递归。 1、确定递归公式 2、确定递归结束条件 四、递归算法的执行过程 1、递推：将复杂的问题（规模为n)的求解递推出一些简单的问题（规模小于n）的求解。此阶段，必须有终止递推的情况。 2、回归：获得最简单情况的解后，逐级返回依次得到稍复杂问题的解。 逐层调用，直到边界（递推） 代入计算，依次返回（回归） 五、递归实现要点: （1）有明确的结束递归的边界条件（终止条件）及终止时的边界值。 （2）函数的描述中包含其本身。 （1）抽象建模 （2）设计算法 （3）编写程序并调试 六、课堂实践： 用递归算法求 n 的阶乘 七、递归的作用 1、分解成规模较小的同类型问题。 2、用递归函数替代多重循环。 3、解决本来就是用递归形式定义的问题。 八、课堂小练： （1）用递归算法求裴波那契数列为：1，1，2，3，5，8，13 ……（填空） def fx(n): if n<2: （1） else: （2） return f print（fx(10)) （2）程序设计并调试： 一个楼梯有n阶，上楼可以一步上一阶，也可以一步上二阶。要求：编写一个程序，输入一个正整数n(表示楼梯阶数)，输出共有多少种不同的走法可以到达第n阶。 九、汉诺塔游戏： 1. 抽象与建模 2.设计算法 3.编写程序 十、课堂小结 1、递归算法的概念 2、递归算法的两个条件和阶段 十一、自我评价 对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油） 评分项自我评价能计算小猴摘桃并总结递归算法的基本思想 3 2 1掌握递归算法的两个条件和两个阶段 3 2 1能自主学习教材并用自然语言、Python语言描述递归算法 3 2 1能够编程实现斐波那契数列、阶乘的递归实现 3 2 1掌握递归算法的设计思路，理解其数学原理和注意事项 3 2 1能用递归算法解决学习、生活中的应用 3 2 1 十一、课后作业 1.求最大公约数：早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法———辗转相除法。 辗转相除法的方法是用较大的数X除以较小的数Y，得到余数Z 如果余数为0，则较小数Y就是两者的最大公约数。 例如：33和9 的最大公约数就是9与6的最大公约数3 以下程序#号划线处代码为（ ） A.a B. gcd(b,a%b) C. gcd(b,a//b) D. gcd(b,a) 2. def zh(n): if n<=1: f='1' else: f=zh(n//2)+str(n%2) return f print(zh(18)) 该程序段运行后的输出值为( ) A、10100 B、10010 C、11010 D、11000 3.有如下数列a1,a2,a3,…的定义如下: a1=1,a2=1 ,…,an =3an-1+2an-2(n>2)。为求该数列的第n项值,现利用递归算法实现,Python代码如下,请在划线处填入合适的代码。 def yuan(x): if x<=2 : return ① else : ② n=int(input(“n=“)) print(yuan(n)) 作业答案： 1. B 2. B 3. ①1 ② return 3*yuan(x-1)+2*yuan(x-2) ... ...