高中信息技术必修一非数值计算第二课时递归与分治教学设计

高中信息技术必修一非数值计算第二课时递归与分治教学设计一、课标定位与教学内容分析本节内容选自教科版高中信息技术必修一《数据与计算》第四单元"计算与问题解决"中的《非数值计算》第二课时。第一课时学生已经建立了"算法不仅能够处理数值运算，同样可以处理文字、图形、逻辑判断等对象"的基本认识，本课时在此基础上向算法策略的纵深推进，聚焦递归与分治两种典型的问题求解思想。课程标准对本模块的要求是：学生在掌握常见程序结构的基础上，能够针对具体问题设计算法，运用恰当的算法策略编程实现问题求解，并能结合实例描述算法执行的过程。递归正是课标中"问题解决过程中体现结构化与模块化思维"的典型载体，而分治思想则是学生日后学习排序、查找等经典算法的认知基石。本课时承担着从"会写顺序、分支、循环"迈向"会用策略求解复杂问题"的关键一跃。需要明确的是，本课时并非单纯的知识传授课，而是一节以思维训练为核心的算法探究课。非数值计算的"非数值"只是表象，其深层意蕴在于：计算的对象可以是非数值的，但计算的思维永远是严谨的、形式化的。学生在本课中要体会的，正是这种以形式化思维驾驭复杂对象的能力。二、学情分析授课对象为高一年级学生。经过前面章节的学习，学生已经能够使用Python编写包含顺序、分支、循环结构的程序，掌握了列表、字符串等基本数据结构的操作方法，完成了第一课时中"报数游戏""百钱买百鸡"等非数值计算实例的学习，初步建立了"枚举求解"的问题处理模式。从认知特点看，高一学生抽象逻辑思维处于快速发展期，但面对"函数自己调用自己"这一反直觉的概念，普遍存在三重障碍：其一，难以想象递归调用时多层函数并存的状态，容易陷入"程序是不是死循环了"的困惑；其二，难以找准递归的边界条件，写出的程序常常因缺少出口而栈溢出；其三，缺乏将大问题拆分为同类小问题的主动意识，习惯平铺直叙地枚举，而非结构化地分解。教学设计中必须正视这些障碍。本课采用"实物模拟—图示追踪—代码实现—对比优化"四步进阶路径，先用看得见的活动建立递归的直观模型，再用调用栈的可视化消除"黑箱感"，最后通过汉诺塔问题的完整求解实现思维的内化与迁移。三、教学目标（一）信息意识：面对复杂问题时，能够敏锐识别问题中蕴含的"自相似"结构，判断其是否适合用递归或分治策略求解，主动将大问题化整为零。（二）计算思维：理解递归的两个必要条件——递归关系与终止条件，能够借助调用栈图示追踪递归程序的执行过程；初步理解分治思想中"分解—求解—合并"三阶段的结构特征。（三）数字化学习与创新：能够编写正确的递归程序解决阶乘、斐波那契数列、二分查找、汉诺塔等问题，能通过实测数据对比递归方案与循环方案的效率差异，形成基于证据的算法评价能力。（四）信息社会责任：在小组协作求解汉诺塔问题的过程中，学会倾听、质疑与重构他组方案，理解算法效率对计算资源消耗的现实意义。四、教学重难点教学重点：递归的两个必要条件及其在程序中的实现；分治思想的三阶段结构。教学难点：递归执行过程的理解，尤其是调用栈的"压栈—回溯"机制；将汉诺塔问题抽象为递归模型的思维跨越。五、教学准备教师准备：多媒体教学系统、Python开发环境、递归调用栈动态演示课件、汉诺塔实物教具若干套（每组一套，含三根立柱和五片不同尺寸的圆盘）、课堂导学单。学生准备：第一课时知识复习，Python环境中预装matplotlib库用于数据可视化。六、教学过程（一）情境导入：一场"传话"引发的思考（约5分钟）上课伊始，教师组织一个微型活动：请坐在教室最后一排的一名学生告诉教师，他所在这一列一共有多少人。规则是：他不能回头数，只能问前排同学"你前面有多少人"，前排同学也采用同样的方式继续向前问，直到第一排同学回答"我前面有0人"，然后答案逐级传回。活动结束后，教师提问：这个过程中，每一个同学做了哪两件相同的事？答案分别从哪里产生、在哪里合并？学生在导学单上记录自己的观察。教师顺势板书：每个人做的事都是"问前面的人，得到答案后加一"，直到第一排给出确切的0。教师点明：这就是本节课的主角——递归。一个问题的答案，依赖于同类的、规模更小的子问题的答案，直到触及一个可以直接回答的"底"。设计意图：用身体参与的具身活动替代干巴巴的概念讲授，让"自己调用自己"有了可感的现实原型。"问—传回—加一"恰好对应递归的"调用—返回—合并"，终止条件则对应第一排的明确回答，概念的结构在活动中已悄然成形。（二）概念建构：递归的两个必要条件（约7分钟）教师将刚才的活动翻译成数学语言。设f(n)表示第n个人前面的人数，那么：f(n)=f(n−1)+1（当n>1时）f(1)=0教师指着这两条式子强调：第一条叫递归关系，它描述大问题与同类的更小问题之间的关联；第二条叫终止条件，也叫递归出口，它是递归停止下沉、开始回传的开关。二者缺一不可——没有递归关系，问题无法分解；没有终止条件，调用将无限进行下去，直至耗尽内存、程序崩溃。随后教师给出本课时的核心判断句式，请学生齐读并记录在导学单上："凡是能写成'大问题等于同类小问题加工而成'且存在最小可直接求解情形的问题，都可以尝试递归。"教师即刻追问检验：阶乘n!能否这样写？学生口答得出：factorial(n)=n×factorial(n−1)（当n>1时）factorial(1)=1设计意图：概念教学不追求定义的背诵，而追求判据的内化。给出清晰的判断句式，让学生获得一把可以带得走的"尺子"，能在新情境中自主识别递归结构。（三）难点突破：让调用栈"现身"（约10分钟）这是本课的思维深水区。教师打开课件，以factorial(4)为例逐帧演示递归调用的完整过程。屏幕左侧是代码，右侧是一块模拟的"栈区"。第一层，factorial(4)被调用，它需要factorial(3)的结果，于是自己暂停，压入栈底。factorial(3)压栈，factorial(2)压栈，factorial(1)压栈。当factorial(1)遇上终止条件，直接返回1。随后开始回溯：factorial(2)拿到1，算出2×1=2返回；factorial(3)算出3×2=6返回；factorial(4)算出4×6=24返回。栈区逐层清空，最终结果诞生。演示中教师刻意放慢回溯阶段，配上一句形象的比喻："下沉时层层托付，回归时层层兑现。每一层都在等，等下一层把答案送回来，再加上自己的那一份。"接着学生动手验证。在Python中输入如下代码，并在函数首行加入输出语句print("进入第",n,"层")，在return前加入print("第",n,"层返回",result)，运行factorial(5)，观察屏幕上"进入"与"返回"两列信息交错出现的次序。学生会发现：所有"进入"连续出现之后，"返回"才开始逆序出现。教师追问：这个输出顺序印证了什么？学生回答：印证了"先一路向下压栈，触底后再逆序回溯"的执行机制。随后教师制造一次"有预谋的故障"：故意删除终止条件，运行程序，让Python抛出递归深度超限的错误。教师引导学生阅读错误信息"maximumrecursiondepthexceeded"，并讨论：生活中有没有类似"没有出口的递归"？学生举出两面镜子相对放置、领导批示"逐级请示"却无人拍板等例子，课堂气氛活跃，而"终止条件不可或缺"的认识也由此刻骨铭心。设计意图：递归难在不可见。动态图示解决"看见"的问题，打印追踪解决"验证"的问题，故障体验解决"敬畏边界"的问题。三管齐下，调用栈从黑箱变为白箱。错误信息不是教学事故，而是被精心设计的教学资源。（四）策略进阶：从递归到分治（约8分钟）教师抛出新问题：在一个有100万名学生的有序名单中查找某位同学的学号，逐一翻看可行吗？学生用第一课时的枚举经验判断：平均要查50万次，太慢。教师引导：名单是有序的。翻到正中间一看，目标学号比中间的小，那么右半边五十万人还需要看吗？学生齐答：不需要。教师继续缩小：再对剩下的左半边取中点……每做一次比较，问题的规模发生什么变化？学生发现：每一次都砍掉一半，范围从100万变50万、25万……大约20次就能锁定目标。教师板书分治思想的三段式结构：分解——把原问题划分为规模更小的子问题；求解——子问题足够小时直接求解，否则递归地继续划分；合并——将子问题的解组合成原问题的解。学生动手实现二分查找的递归版本。教师提供程序骨架，学生补全关键语句：defbinary_search(lst,target,low,high):iflow>high:return1mid=(low+high)//2iflst[mid]==target:returnmideliflst[mid]>target:returnbinary_search(lst,target,low,mid−1)else:returnbinary_search(lst,target,mid+1,high)补全前，教师要求学生在导学单上先回答两个脚手架问题：这段代码的终止条件有几个，分别是什么？每次递归调用时，问题规模是通过哪两个参数缩小的？回答正确后方可动手编码。运行测试后，学生用time模块对比二分查找与顺序查找在十万条数据上的耗时，实测差距的震撼远胜任何说教。设计意图：分治不是与递归并列的另一个知识点，而是递归的上位策略。二分查找是体会"以智取胜"最经济的案例。先想后写的要求，意在扭转学生"拿到题就敲键盘"的冲动，把思维置于编码之前。（五）综合运用：破解汉诺塔之谜（约12分钟）各小组领取汉诺塔教具，先尝试移动3片圆盘，记录移动步骤，再挑战4片、5片。几分钟后教室里的讨论声渐低——片数一多，人脑的工作记忆明显吃紧。教师此刻介入："你们的困难恰恰是本课的价值所在。人脑记不住的状态，交给算法。请观察：要把n片盘子从A柱移到C柱，本质上需要哪三步？"小组研讨，教师巡视点拨：关注最大的那片盘子。它要想到C柱，前提是什么？学生顿悟：上面n−1片必须先全部挪到B柱腾地方。于是三步结构浮出水面。把n−1片从A经C移到B；把第n片从A直接移到C；把n−1片从B经A移到C。其中第一步和第三步，又是同一个问题的更小版本——递归关系就此确立，而n等于1时直接从A移到C即是终点。学生据此写出代码：defhanoi(n,a,b,c):ifn==1:print(a,"→",c)returnhanoi(n−1,a,c,b)print(a,"→",c)hanoi(n−1,b,a,c)运行hanoi(3)，输出七步移动序列，小组用实物教具逐步核对，完全吻合。教师请各组将n从1递增到10，记录移动次数，寻找规律，学生归纳出2的n次方减1的通式。教师补充一段史料：传说中64片金片的汉诺塔，按每秒移一片计算，需要约5849亿年——学生哗然之际，教师点拨："递归给了我们把复杂问题说得简洁的能力，但言简不等于算得快。算法的时间代价，同样是算法素养的一部分。"设计意图：汉诺塔是递归思想的最佳体操。实物操作制造认知困境，"关注最大盘"的点拨架起抽象阶梯，实测数据引出规律归纳，史料则注入人文温度并埋下算法复杂度的种子，为后续学习预留接口。（六）课堂小结与结构化梳理（约3分钟）教师请一名学生借助板书回顾全课脉络：从一个传话游戏出发，建立了递归的两要素——递归关系与终止条件；通过调用栈的追踪理解了递归"先压栈后回溯"的执行机制；在二分查找中掌握了分治"分解—求解—合并"的三段式；最终在汉诺塔中体验了递归建模解决复杂问题的完整过程。教师收束全课："递归的本质，是对'同类'二字的信任——相信小一号的问题会被同样的方法解决，于是你只需要处理好手头这一层，和一个可靠的出口。"（七）分层作业布置（约1分钟）基础层：用递归实现斐波那契数列第n项，并用打印语句追踪调用过程，画出n等于5时的调用树。提高层：对比递归法与循环法计算斐波那契第35项的耗时，结合调用树解释性能差异的原因。挑战层：研究"快速排序"的基本思想，尝试说明它如何体现分治的三段式结构，下节课用两分钟向全班汇报。七、板书设计主板书居中呈现本课概念骨架：左侧为"递归"，下挂两要素"递归关系、终止条件"，配factorial递推式；中部为调用栈示意图，箭头标注"压栈↓回溯↑"；右侧为"分治"，下挂"分解—求解—合并"，配二分查找与汉诺塔两个实例。副板书区留作课堂生成记录，粘贴各小组汉诺塔步数实测数据。八、教学评价设计本课评价贯穿全程。活动导入环节通过观察学生话语中的关键词判断概念前认知；调用栈环节依据学生对打印输出次序的解释完成形成性评价；二分查找环节以"两个脚手架问题"的回答质量作为思维可见化的证据；汉诺塔环节采用小组互评，评价维度包括建模的正确性、代码的规范性与数据归纳的发现