数据结构（Python Java）（微课版） 教案 -单元4递归

教案课程名称数据结构与算法设计课程代码总学时64课程负责人任课教师

单元教案授课日期年月日—月日授课地点授课班级班级人数教学单元单元4递归教学时数4教学目标AOB1:掌握计算机程序设计中的线性表、栈、队列、树和图的逻辑结构与存储结构。了解递归的数据逻辑组织结构；AOB3:掌握对算法的科学分析方法。BOB1:能根据实际问题中的数据特性选择适当的数据结构；EOB1:掌握使用搜索引擎、论坛、帮助文档、课外书籍等方法解决学习中出现的问题；教学方式混合式教学评价方式课堂考勤（20%），课堂活动参与程度（30%）线下课堂教学参与程度（50%）教学资源1.算法与数据结构（Java语言描述），陈媛，清华大学大学出版社2.电脑50台（含eclips）;3.网络学习资源：/forums/ST_Arithmetic：课程平台网址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea单元教学设计第一次课（2学时）教学内容4.1递归的概念若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。4.2递归设计：递归问题，必须符合以下三个条件可以把一个问题转化为一个新的问题，这个新的问题的解决方法与原问题的解法相同，只是所处理的对象有所不同；可以通过转化过程使问题得到简化；要有明确的结束递归的条件，否则递归将会无止境地进行下去，直到耗尽系统资源，必须要有终止递归的条件。适用递归解决的问题1.定义是递归的2.数据结构是递归的3.问题的解法是递归的递归的执行过程递归设计步骤1.对原问题f(s)进行分析，假设出合理的“较小问题”f(s’)；2.假设f(s’)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s’)的关系；3.确定特定情况，即（f(1)或f(0)）的解，由此作为递归出口。教学重点递归设计教学难点递归设计教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1平台发布任务2考勤1考勤讲授（80分钟）1.递归的概念（10分钟）2.递归设计（5分钟）3.适用递归解决的问题（50分钟）4.递归的执行过程（10分钟）5.递归设计步骤（5分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务第二次课（2学时）教学内容递归的评价递归的优点：可解决复杂问题；可缩短程序代码、提高编程效率递归的缺点：不能提高程序的运行效率递归运行效率问题斐波那契数列的递归调用树递归与回溯回溯法是从问题的某一种可能出发，搜索从这种情况出发所能达到的所有可能。当这一条路走到“尽头”的时候，再倒回上一节点，从另一个可能出发，继续搜索。回溯是一种思想，递归是一种解决问题的方法。回溯可以用递归来实现，也可以不用递归实现。迷宫问题迷宫中设置很多隔壁，对前进方向形成了多处障碍。假设迷宫的每个岔路口只有东南西北四个方向或是这四个方向的子集。回溯法思想：一种不断试探且及时纠正错误的搜索方法。；从入口出发，按某一方向向前探索，若某处可以到达，则到达新起点；否则试探下一方向。；若所有的方向均没有通路，则沿原路返回到前一点，换下一个方向再继续试探，直到所有可能的通路都试探到。；结果是或找到一条通路，或无路可走又返回到入口点。递归实现：从入口出发，每到一个结点（岔路口），按东南西北的秩序访问相应方向的下一个结点，如果相应方向没有可以访问的结点，则访问下一个方向。如果四个方向全被访问完，则返回到前一个结点。直到找到出口或回到入口。递归的关键问题为防止递归的无休止调用，在递归函数中要及时返回，这是结束条件的作用；在所有的递归函数中都有一个终止递归的条件判断；递归函数可以简化程序，但一般不能提高程序的执行效率。教学重点递归的评价教学难点递归的评价教学流程教学环节教师活动学生活动讲评和考勤（5分钟）1.平台发布任务2.考勤1.考勤讲授（60分钟）1.递归的评价（10分钟）2.递归运行效率问题（15分钟）3.递归与回溯（15分钟）4.迷宫问题（15分钟）5.递归的关键（5分钟）1.积极回答教师提问2.认真思考、记录关键内容3.积极参与课堂的讨论和互动代码实现演示（20分钟）1.斐波那契数列的递归调用树的代码实现（20分钟）1.认真思考、记录关键内容总结与发布课后任务（5分钟）1.总结课堂内容以及在练习过程中出现的，问题。2.布置课后任务1.思考教师总结2.记录课后任务教学效果与反思根据单元测验结果，80%的学生教好掌握了教学内容，达成了单元教学目标。其中教学目标AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3达成情况较好，但EOB1、EOB3达成情况一般。结合学生的课堂练习，在线测试等教学活动的结果来看，课堂出勤比较好，没有缺课的情况；课堂练