高中一年级信息技术非数值计算之递归算法与分治思想教学设计

高中一年级信息技术非数值计算之递归算法与分治思想教学设计一、教材与学情分析本课选自教科版（2019）高中信息技术必修1《数据与计算》第四单元第三节"非数值计算"的第二课时。第一课时学生已经历了用二分查找解决有序数据查找问题的完整过程，初步体会到算法不只是处理数字运算的工具，更能解决查找、排序、策略规划等广义问题。本课时在此基础上升维：从"逐步逼近"的二分思想走向"自我调用、化大为小"的递归思想，以汉诺塔问题为核心情境，引导学生认识递归算法的结构特征、执行机制和适用条件。高一学生逻辑抽象能力正处于快速发展期，具备第一课时二分查找的学习经验，已掌握Python基本语法中的函数定义与条件语句。但学生普遍存在两处认知障碍：一是难以想象"函数调用自身"这种反直觉的执行方式，容易陷入"无限循环"的思维误区；二是缺少拆分问题的意识，面对复杂任务习惯硬碰硬地逐一处理，不会主动寻找"同类子问题"。本课的教学设计正是围绕这两道坎搭建支架。课标对本模块的要求是：从实际情境出发，认识算法在解决问题中的重要作用，体验用程序实现算法的过程，发展计算思维。本课落实学科核心素养的着力点在于：计算思维中的问题分解与抽象建模，信息意识中的算法优化意识。二、教学目标第一，学生能说出递归算法的两个基本组成——递归调用与终止条件，能用自己的语言解释递归"递进去、回归来"的执行过程。第二，学生能通过分析汉诺塔问题，抽象出"将n层问题转化为n−1层问题加一步操作"的分治策略，并能写出对应的递归函数代码。第三，学生能通过对比二分查找与汉诺塔的解决思路，归纳"把大问题化为结构相同的小问题"这一共性思想，初步形成分治思维的迁移能力。第四，学生在小组协作调试递归程序的过程中，养成先推理后验证、先小规模后大规模的实验习惯，体验算法设计的严谨与优雅。三、教学重点与难点教学重点：理解递归算法"自己调用自己"的运行机制，掌握递归函数中递归体与终止条件缺一不可的结构规律。教学难点：对汉诺塔问题进行递归抽象，将三根柱子上多层圆盘的移动问题，正确分解为规模更小的同类子问题，并用代码精确表达。四、教学准备与教学策略教师准备三层汉诺塔实物教具一套、演示动画课件、安装Python环境的机房。学生人手一份导学案，内含空白递归调用展开图填写表。教学策略采用"实体操作—思维抽象—代码实现—对比迁移"四段递进路径，以问题链驱动，以小组探究为主要组织形式，教师以示范和追问介入关键节点。五、教学过程（一）情境导入，激活旧知（5分钟）上课伊始，教师在讲台摆出三根立柱和三个带孔圆盘的实物教具，提出挑战：把A柱上由大到小叠放的三只圆盘，整体搬到C柱，每次只能移动一只盘，且任何时候大盘不能压在小盘上。请一名学生上台操作，其余学生默数移动步数。学生很快完成任务，答案是7步。教师顺势追问两个问题。第一，上一节课我们学的二分查找，效率是逐次减半，查找n个元素最多需要多少次比较？学生回忆并回答：k次由2ᵏ≥n决定。第二，如果圆盘不是3只而是64只，按传说中每秒移动一次计算，需要多久？教师给出约5800亿年的数字，教室内一片惊叹。教师点明：这个数字背后藏着一个比二分查找更具威力的思维方式——把64只盘子的问题变成63只盘子的问题，一直变到只剩1只。这就是今天要研究的递归。板书课题：递归算法与分治思想。设计意图：实物操作为抽象思维提供直观抓手，"5800亿年"制造认知冲突，让学生产生"必须找到通用解法"的内在需求，同时用二分查找的旧知为新知的分治思想埋下伏笔。（二）动手试错，感知规律（8分钟）学生四人一组，每组利用纸片自制"三根柱、三只盘"，完成任务单上的两个活动。活动一，移动2只盘，记录每一步；活动二，移动3只盘，记录每一步，并填写表格：盘数1、2、3时最少步数各是多少。各组汇报，教师将结果汇总到黑板：盘数1时1步；盘数2时3步；盘数3时7步。教师引导学生观察数列1、3、7，猜测下一步。多数学生能发现规律：后一项是前一项的2倍加1。教师请学生验证对4只盘的猜想是否为15步，并用实物验证其中部分步骤。关键追问出现：为什么盘数是3的时候恰好是7？7和"先移走上面2盘、再移最大的盘、再把2盘挪回来"之间是什么关系？教师让学生在任务单空白处画示意图，把"3盘问题"拆解成三个阶段：阶段一，把上面2只盘借助C柱移到B柱；阶段二，把最大的盘从A移到C；阶段三，把2只盘从B借助A移到C。学生画出后恍然大悟：阶段一和阶段三本身就是2盘问题，只是起点和终点柱不同。教师板书这个结构，并强调一句话：7=3+1+3。设计意图：让学生亲手发现"3盘问题内部藏着2盘问题"，这种"自相似"结构是递归的本质所在。先操作后抽象，符合高一学生的认知顺序。（三）抽象建模，定义递归函数（10分钟）教师引导：我们已经发现，移动n只盘分三步走——先把上面n−1只盘从源柱移到中转柱，再把第n只大盘从源柱移到目标柱，最后把n−1只盘从中转柱移到目标柱。而"移动n−1只盘"和"移动n只盘"是同一类问题，完全可以交给同一个方法去做。在任务单上，教师与学生共同补全程式化的描述。定义：设函数move(n,from,temp,to)表示把n只盘从from柱借助temp柱移到to柱。当n等于1时，直接输出"把盘从from移到to"。当n大于1时，依次执行三件事：move(n−1,from,to,temp)；输出移动大盘；move(n−1,temp,from,to)。教师组织学生辨析两个核心概念。其一，递归调用：函数在内部又一次使用了自己，参数从n变成n−1，规模缩小。其二，终止条件：当n等于1时不再调用自己，直接输出结果。教师设置问题：如果删掉"n等于1时直接返回"这一行，会发生什么？学生思考后回答：n会不断减下去，变成0、负数，永不结束。教师确认：终止条件是递归的生命线。随后教师用粉笔展示n=3时的调用展开图，用缩进表示调用层级：move(3)展开为两个move(2)和一步操作，每个move(2)再展开为两个move(1)和一步操作。学生观察图后完成填空：整个展开中，叶子节点（move(1））共有多少个？答案是7个，对应7次移动，与实物实验完全吻合，思维与操作互相印证。设计意图：把实物操作中的三阶段规律，形式化为函数定义，完成从动作到符号再到代码的前两跳。调用展开图把"看不见的执行流"变成看得见的树形结构，化解递归难懂的症结。（四）代码实现与运行验证（10分钟）教师在大屏逐行呈现Python实现：第一行定义函数：defhanoi(n,a,b,c)，其中a是源柱、b是中转柱、c是目标柱。函数内部：ifn==1:print(f"第{n}号盘{a}→{c}")；else部分依次调用hanoi(n1,a,c,b)、输出最大盘的移动、hanoi(n1,b,a,c)。学生打开环境，敲入代码，分别运行hanoi(2,'A','B','C')和hanoi(3,'A','B','C')，对照自己刚才手工记录的移动步骤逐条核对。多数学生会惊喜地发现程序输出与自己操作的顺序完全一致。教师接着布置三项探究任务。任务一，运行hanoi(4)，数一数输出了多少行，验证是否与猜想的15步一致。任务二，故意把程序中n==1的判断改成n==0，或者删掉终止条件，观察运行结果，体会"栈溢出"报错，理解为什么必须设置终止条件。任务三，在函数内部第一行加上一条打印语句print("进入",n)，再运行hanoi(3)，观察"进入3、进入2、进入1"然后再退出的顺序，直观感受"递进去、回归来"。小组内检查每位成员的三项结果，由组长向教师报告发现。教师巡回指导，重点帮助对调用顺序仍困惑的小组，让他们对照黑板上的调用展开图逐行比对输出。设计意图：试错的任务二是精心设计的反面教学，"让程序出错"比"让程序正确"更能让学生记住终止条件的存在意义。任务三的追踪打印把递归的执行机制透明化。（五）对比升华，提炼分治思想（7分钟）教师组织学生完成一张对比表格，纵栏三个维度：问题如何拆分、拆到什么程度为止、每次拆分后做什么。横栏两列：二分查找与汉诺塔递归。师生共同填写后得出结论：二分查找把查找区间对半切分，直到找到目标或区间为空；汉诺塔把n盘问题拆成n−1盘问题，直到只剩1盘。两者面貌不同，灵魂相同——都把一个复杂问题转化为结构相同而规模更小的问题，这种策略称为分治。教师补充说明：排序中的归并与快速排序、大整数乘法等经典算法，都建立在同样的思想之上，这是计算机科学中一条贯穿始终的主线。教师再布置思辨问题：递归这么好，是否所有问题都该用递归？教师给出对照例子：计算阶乘既可以用递归也可以用循环。请学生说出递归的代价——每次调用都要保存现场，占用内存，层数太深会溢出。归纳结论：选用递归的前提，是问题天然具有自相似结构，且拆分收益大于调用开销。设计意图：单点知识容易遗忘，放进对比框架才能获得结构化的长久记忆。让学生同时看到递归的力量和边界，防止片面的算法崇拜，培养权衡意识。（六）分层练习与应用迁移（7分钟）基础层面向全体：给出函数deff(x):若x等于0返回0，否则返回x+f(x−1)，求f(5)的值，并写出调用过程。全体学生独立完成，同桌互批，答案15。提高层面向多数：修改汉诺塔程序，增加一个全局计数变量，让程序在输出每步移动的同时，最后一行打印"共移动X次"，并验证n只盘的移动次数满足M(n)=2ⁿ−1。学生运行n从1到5，依次得到1、3、7、15、31，与公式逐项吻合。拓展层供学有余力者尝试：用递归实现二分查找。函数定义为bisearch(lst,low,high,key)，当low大于high时返回−1，否则取中间位置比较，小于则向左半区递归，大于则向右半区递归。这是对第一课时的递归化改造，把两节课的知识在更高层次上焊接起来。教师巡视收集典型答案，选择一份提高层作业和一份有代表性错误的作业在实物投影上展示点评，着重讲清全局计数变量的作用域处理。设计意图：三层任务对应不同认知水平，保证保底不封顶。拓展题把两节课打通，体现单元整体教学的连贯性。（七）课堂小结与作业布置（3分钟）教师请两名学生用一句话总结本课收获。预设的表达包括：递归就是一个函数调用自己来把大问题变小；递归必须有终点，否则就跑飞出去了。教师在此基础上凝练板书：一看自相似，二定终止线，三写小调用。作业分两项。第一项，完成导学案上的递归追踪题：手绘fact(4)阶乘递归的调用与返回全过程。第二项为选做，查阅"斐波那契数列"的递归实现，体会其中出现的重复计算问题，思考为什么递归算fib(40)会明显变慢，为后续学习奠基。六、板书设计主板书分三区。左区：汉诺塔规律表——盘数1步数1，盘数2步数3，盘数3步数7，猜想M(n)=2M(n−1)+1=2ⁿ−1。中区：核心结构式——n盘问题=(n−1)盘问题+一步移动+(n−1)盘问题。右区：递归两大要素——终止条件与自我调用，附一句警示语：无终止，即深渊。七、教学评价设计评价贯穿全程，采用三种方式。过程性评价：观察小组操作汉诺塔时的讨论质量与记录完整性，计入课堂表现。表现性评价：三项探究任务和分层练习的完成度，用"达成/部分达成/待改进"三档记录在导学单上。诊断性评价：课后递归追踪题，重点检查学生能否正确画出"先递到最深、再逐层返回"的执行顺序，作为下节课开端的