递归算法的实现教学设计

1、递归算法教学设计蚌埠新城实验学校徐田柱一、教学三维目标知识与技能：1、理解什么是递归算法，学生用递归算法的思想分析问题、解决问题2、能够应用自定义函数方法实现递归算法的编程过程与方法：学生参与讨论，通过思考、动手操作，掌握递归算法情感态度与价值：结合数学中的实例，激发学生的数学建模的意识，培养学生多维度的思考问题和解决问题。二、教学重点与难点重点：理解什么是递归算法，学生用递归算法的思想分析问题、解决问题应用自定义函数方法实现递归算法的编程难点：应用自定义函数方法实现递归算法的编程三、教学策略教递归算法的实现思想是比较抽象， 比较理论化的教学内容。 本着培养学生的发现问题、分析问题、解决问题的

2、意识与能力入手。知识主要是靠学生学会的，学习就是发生在学生头脑的建构。教师必须明确学生是学习的主体， 研究学生学习的真实心理活动，分析其认识过程、机制及心智变化。确定教学方法。四、教学环境网络教室，教学软件 DEV C+ ，大屏幕投影；五、教学资源准备从本学科的特点、 学生的认知水平及学习心理特征， 更好的激发学生的学习动机与信心， 为保持学生的学习激情， 设计了一系列难度层层递进的例题和练习。六、教学过程(一)情景导入 ,提出课题师：从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚在讲故事，他讲的故事是：从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚在讲故事师：

3、这个故事体现了我们以前提到过的哪种程序设计算法？生：递归算法师：是的，引入课题，本节课我们就来深入学习递归算法。设计意图：用故事引入课题，便于学生理解。(二)新课探究，导出递归算法程序设计思想( 1)例题 1：求：f(n)=1+2+3+ (n-1)+n学生很容易想到以前学过的迭代算法：s=0;For(i=1;i<=n;i+) s=s+i;老师提出递归表达式：1 当n 1时n f(n 1) 当 n 1 时递归算法：long f（int n）if （n=1） return 1;else return n+f（n-1）;引导学生思考， 如果把“ + ”号改成“ - ”、“*”或“ /”， 递归

4、表达式如何更改， 递归算法如何改。 （学生思考，让学生学会举一反三、触类旁通） 。（三）深入学习递归算法的实现（ 1）展示递归算法的演算过程，分析演算过程，引导学生总结出，递归算法的两个必备条件：1、递归分为递推与回归两个过程2、递归必需要有结束条件递归算法的实现方式：递归算法是数据层层调用实现的，函数先由上向下调用，当达到最底层后，再将数值层层向上返回。 （在函数层层调用的过程中，参数的改变）（ 2）通过上面的分析，大至的递归算法实现思想我们了解了，那么要思考在编程过程中如何解决两个问题？1、怎么将问题推下去？2、怎么将结果回归？设计意图： 在学生初步认识递归算法的演算过程及特点以后， 提出

5、递归算法程序设计实现的关键问题， 层层深入的引导学生思考问题， 培养学生分析和发现 问题的能力。3）展示递归算法自定义函数框架，并分析。设计意图：为下面进行操作练习奠定思维框架。4）思考练习：楼梯有n 阶台阶 ,上楼可以一步上1 阶,也可以一步上2 阶,编一程序计算共有多少种不同的走法。假设到达第 n 个台阶的走法共有f（n） ，那么很容易得到一个数学递归表达1时2时2时1f(n)2f(n - 2) f( n 1)请同学们用算法将这个递归表达式描述出来。设计意图：培养学生分析问题、解决问题能力，煅练学生“数学建模”能力，让学生通过实践和思考找出本题的关键，并引出递归算法的解题思想。（四）回顾例

6、题 1 和思考练习引导学生思考刚才的例题和练习， 这两个问题完全可以使用递推的原理去解决，用了递归方法以后反而要不断的回溯，这样的话效率反而降低。总结出：递归算法使得计算机资源耗费大，效率偏低。 （缺点）设计意图：培养学生深入思考，既然递归算法资源消耗大，效率低，为什么还使用递归算法呢。为后面的问题做铺垫。例题 2：汉诺塔 （Tower of Hanoi） 问题 。假设有二根木桩分别为 A、B和Co在木桩A上安置了 N个圆盘，由上到下编号为1, 2, - N,编号越大的圆盘直径也越大。现需要将 A木桩上N 个圆盘借助 B 木桩移到 C 木桩上，且必须按照下述移动规则：1 .直径较小的圆盘永远置

7、于直径比较大的圆盘上;2 .圆盘可任意地由任何一个木桩移到其他的木桩上;3 .一次只能移动一个盘子。解题思路：如果 n = 1 ，则将这一个盘子直接从A 柱移到 C 柱上。否则，执行以下三步：1. 用C 柱做过渡，将A 柱上的(n-1)个盘子移到B 柱上；2. 将 A 柱上最后一个盘子直接移到 C 柱上；3. 用A 柱做过渡，将B 柱上的(n-1)个盘子移到C 柱上。递归表达式：f (n, A, B, C)1时2时ACf(n 1,A,C,B), A C, f(n 1, B, A C)当 n算法：void f(int n,char a,char b,char c)if (n=1) cout<<a<<“-> ” <<c;elsef(n-1,a,c,b);cout<<a<< “-> ” <<c;f(n-1,b,a,c);设计意图：进一步培养学生发散思维，对于某些问题，如汉诺塔、快速排序用递归思想解决起来就特别容易， 特别是人工智能问题， 就依赖于递归提供解决方案。