信息技术选修1 数据与数据结构5.2 迭代与递归精品表格教学设计

课程标准

和

教学目标

递归

教材内容：5.2迭代和递归　之　递归

适应的课程标准：

1.7 通过实现数据的排序和查找，体验迭代和递归的方法，理解算法与数据结构的关系。

教学目标：

●能结合具体程序实例，掌握递归函数的定义。

●能够运用递归的思想和方法，编程实现“汉诺塔”。

指向的核心素养：

●信息意识：学生能够结合生活中的实例描述数据的内涵与外延，能够将有限制条件的、复杂生活情境中的关系进行抽象，有意识地选择恰当的数据结构表达数据的逻辑关系。

●计算思维：能够从数据结构的视角审视基于数组、链表的程序，解释程序中数据的组织形式，描述数据的逻辑结构及其操作，评判其中数据结构运用的合理性；能够针对限定条件的实际问题进行数据抽象，运用数据结构合理组织、存储数据，选择合适的算法（排序、查找、迭代、递归）编程实现、解决问题。

●数字化学习与创新：要使学生熟练地运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。

●信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。

学习环境：有教学控制软件的多媒体机房，python编程环境。

建议课时：1课时

教学活动设计

教学环节

教学过程

设计意图

情境导入

导入1：展示“俄罗斯套娃”，略加简介：相传俄罗斯民族有两家表亲相邻，表兄妹童年相伴长大，后来表兄远走它乡，由于思念家乡的表妹，每年做木娃娃，一年比一年做的娃娃大。数年后，他回到了家乡，将娃娃送给了表妹，后人模仿传称套娃，又叫吉祥娃娃。引入递归的思想。

导入2：分形图案生成（递归算法），选择IDLE中的Help菜单——Turtle Demo——Fractalcurves，简介其基本原理。

通过导入生活中的递归案例，以便顺利过渡到递归算法思想的分析。

学习任务一：阶乘问题

●学习任务一：阶乘问题

问题：利用递归算法求n的阶乘（n!=1×2×…×n）。由数学知识可知，n阶乘的递归定义为：它等于n乘以n-1的阶乘，即n！=n*(n-1)!,并且规定0的阶乘为1。设函数fac(n)=n!，则fac(n)可表示为：

展示一般递归函数定义方法：

描述递归过程：

对应地，可以跟踪递归函数中参数n的变化情况：

设问：

前面，我们已经学习过斐波那契数列的递推公式：

 a1 = 1

 a2 = 1

an=an-1+an-2(当n>2时)

你能编写对应的递归程序由计算机计算一年后的兔子总数吗？

参考程序：

Fibonacci程序递归算法：

教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。特别地，如当规模N=0或1时，能直接得解。因此，在设计递归算法时，要满足两个条件，即要确定递归公式和递归结束条件。

设计意图：递归是程序设计里面比较高级的技术。递归函数的定义比较特殊，它基于自己定义自己。初学者感觉困惑的地方就在于：这种定义方法有意义吗？这是一种循环定义吗？建议使用简短例子，介绍递归函数的定义方法，递归公式的建立，以及递归结束条件。引用上节已经练习过“兔子有多少只？”程序实例，学生动手写递归程序，初步体会“迭代算法”与“递归算法”的区别。通过对递归程序的执行过程的仔细分析，同时跟踪递归函数中参数的变化，引导加深概念理解，最后总结递归算法的执行过程中的递推和回归两个阶段。

自主学习

学生自主编写程序，教师及时跟踪、辅导、点评、总结

参考程序：

Fibonacci程序迭代算法一：

Fibonacci程序迭代算法二：

算法一通过数组的形式实现，它与数学中“数列”的关系紧密，便于与数学学科横向联系，算法二设置了三个变量，巧妙地用了a，b，c三个变量来中转兔子的数量，初始时，a,b都为1，从第三个月开始，c表示总数，a表示新生下来的兔子或者前两个月的时候就存在的老兔子，也就是an-2，b表示前一个月底已经存在的兔子，也就是an-1，如此滚动向前计算。体会其中a和b的变化情况。算法二更集中地体现了计算机中迭代算法的特点。

对学生编程中不同的实现方式，即时发现、即时点评，可以让学生互评、自评，激发大家探索与思考。

学习任务二：汉诺塔游戏

●学习任务二：汉诺塔游戏

汉诺塔游戏更为复杂，为了更好地理解这个问题。教材对此问题进行了详细的分解。一是抽象与建模；二是设计算法；三是编写程序。上一节中课后习题第5题，我们专门设置了对应的习题，学生应该对这个问题有所了解。建议本块内容教学按照学生的思维规律，由具体到抽象，由简单到复杂，依序进行。

1.抽象与建模

为了明确规则，推演过程，选择IDLE中的Help菜单——Turtle Demo——Minimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程。

考虑一般情形，为了将n个盘子从A柱经过B柱移动到C柱，可建立如下模型：

设计意图：递归是计算思维能力之一。首要是寻找和发现问题的规律与内部结构。能够由具体情况概括出一般规律，通过本问题的细致分析，学生可以体会到抽象与建模的基本过程。

2.设计算法

根据上述抽象与建模可以发现，原来与n有关的问题变成了与n-1有关的问题，重复这个过程，每次n减1，最后当n=1时，直接移动该盘子。因此，该问题可采用递归算法来实现，即：

（1）定义一个实现盘子移动的函数move。如将n个盘子从A柱经过B柱移动到C柱，可调用函数move(n, a, b, c)，其中，n表示A柱上的盘子个数，a、b、c分别表示A柱、B柱、C柱。

（2）将n-1个盘子从B柱经过A柱移动到C柱，可以分解成如下递归调用：

move(n-1, a, c, b)

a→c

move(n-1, b, a, c)

（3）当n=1时，直接移动盘子，递归结束。

设计意图：难点在于根据模型写出对应的程序实现，而本算法中的函数参数是疑难点。实参与形参的区别、参数在每次递归中变化情况，可以略加展开说明。

3. 编写程序

根据算法，得到的程序及测试效果如下：

计算思维能力的培养，首要是问题的抽象与建模。它是决定问题解决的关键之一。其次，算法设计是重点与难点。可以在模型指导下配合讲解递归函数的设计，鼓励学生自己动手编写程序。尝试修改函数中的次数参数，观察参数变化带来不同的效果。

拓展学习

递归程序一般具有如下结构：

（1）首先指出数据规模“最简单”的情况，数据如何进行计算。

（2）数据规模“较复杂”的情况，可以归结为“较简单”的数据计算。

递归程序的程序正确性与数学归纳法紧密联系。数学归纳法的基本证明过程：

（1）验证当n = 1（或其它值）时，递归式成立。

（2）假设当n = k时，递归式成立，证明n = k+1时，递归式亦成立。

具体使用递归时应避免“无限递归”的情形。如果一个递归永远也达不到基准情形，则它会永远继续递归调用，而程序也永不停止。这个现象称为“无限递归”。下面是一个会引起无限递归的最简单的函数：

Def recurse():

    Recurse()

无限递归的函数并不会真的永远执行，python运行环境会在递归深度达到上限时报告一个出错信息：“RuntimeError:Maximum recursion depth exceeded”，即“运行时错误：超出最大递归深度”（默认上限为1000）

递归设计是一个难点，而它的基本思想原理与数学归纳法密切相关，同时还应当注意“无限递归”问题。

课堂小结

知识梳理：

1. 递归代算法的基本思想与应用；

2. 递归算法的实现技术；

3. 递归算法的数学原理与注意事项。

迭代表达式的建立是难点，课后作业提供了相应练习。

作业布置

基础作业（面向所有学生）：

完成课本“思考与练习”第4题

本节安排了三道题目，也可以结合本章习题布置作业。

课后作业是课堂学习的延伸，是巩固和升华知识点的有效途径。

教学设计思路

本课内容为递归，建议分配1课时完成。递归在解决一类问题时十分有用，往往描述简洁，易于理解，并能极大地减少程序代码量。它的关键在于识别出内在的递归结构。

它与高中数学教材中的“数学归纳法”原理紧密相连，了解这个原理更有助于知识内容的理解与掌握。

首先，启发学生对“递归”思想有所感悟，可以引用生活的事例（比如俄罗斯套娃），或者从身边的小事讲起，例如“帮拿作业本”。

其次，以阶乘为例，介绍其递归公式，引入递归函数的定义。然后重点强调设计递归算法时，要满足两个条件：确定递归公式和递归结束的条件。

再次，为进一步引导学生使用递归算法来解决问题，可以使用汉诺塔游戏为例，重点放在问题的分解与综合上，重点在于提示其内在的递归结构。

本节主要内容为递归。学生对于递归相对陌生，理解难度较大，建议从抽象与建模、设计算法、程序实现三个方面，深化细化，引导学生理解并掌握递归算法。

针对

核心素养培养的

设计考虑

信息意识、信息社会责任：本节课在导入时选择了两个案例，导入一“俄罗斯套娃”来自生活，导入二“分形图案生成”，递归算法可以创造出美妙图案；这些实例目的是引起学生探究的兴趣，提示学生意识到递归算法思想的奇妙运用，教师引导总结“即大问题的解决中嵌套着原问题相似的规模较小的问题”，目的是能够启发思考、归纳出递归算法的普遍运用，增强学生对此类问题的敏感性，对递归算法的思想有初步的意识。

计算思维：本节中的递归算法即为计算思维的核心之一，主要表现在如下四个方面：一是如何将一个复杂的问题简单化处理，这体现了简洁性；二是对于每次简化的问题，其表达方式与原方式保持一致，反映了结构性；三是问题解决是有终止的，简化到一定程度，一定是可以解决的，反映了构造性；四是可以用有限的步骤处理近于无限功能的方法，体现了简约性。

数字化学习与创新：本节选择IDLE中的Help菜单——Turtle Demo——Minimal_Hanoi，使用现成的数字化学习工具，直观展示“迷你汉诺塔”游戏的动画过程，为典型的数字工具应用。