下载文档原格式
“递归算法与实现”的教学设计引言：递归算法是计算机科学中非常重要的概念之一，也是理解计算机程序设计的基础。
本文旨在设计一堂递归算法与实现的教学课程，通过理论讲解、实践演练和互动讨论等多种教学手段，帮助学生全面掌握递归算法的概念、原理和实现方法。
一、教学目标：1.了解递归算法的基本概念、特点及应用场景；2.掌握递归算法设计的一般方法和技巧；3.学会使用编程语言实现递归算法；4.培养学生的问题分析和解决能力，提高编程思维。
二、教学内容和流程：1.理论讲解（40分钟）a.递归算法的基本概念和特点；b.递归算法的应用场景；c.递归算法的设计方法和技巧；d.递归算法的时间复杂度分析；e.递归算法中常见的问题和注意事项。
2.实践演练（60分钟）a.设计一个典型的递归算法例子，如计算斐波那契数列、阶乘等；b. 编程语言实现递归算法，如使用Python编写斐波那契数列的递归算法；c.演示和讲解实现过程，引导学生理解和掌握递归算法的实现方法；d.练习程序调试和改进，引导学生思考如何优化递归算法的效率。
3.互动讨论（30分钟）a.分组讨论课程中的问题和难点，并总结解决方法；b.学生分享自己设计和实现的递归算法，互相学习和评价；c.引导学生思考递归算法与非递归算法的异同以及选择的依据。
4.课程总结（10分钟）a.强调递归算法的重要性和应用价值；b.总结学生在课程中的收获和学习重点；c.提醒学生继续深入学习和实践，不断提升编程能力。
三、教学手段和资源准备：1.板书和投影仪：用于展示递归算法的图形、代码和思维导图等；2. 编程环境和语言：提前安装好适合的编程环境和语言，如Python、Java等；3.实例和题目：准备一些典型的递归算法问题，供学生练习和巩固；4.小组讨论：将学生分组，进行问题分析和解决思路的讨论。
四、教学评估方法：1.课堂互动：通过学生的提问、回答和讨论，了解学生对递归算法的理解和应用程度；2.实践成果：根据学生的编程实践成果，评估其递归算法设计和实现的正确性和效率；3.课后作业：布置相关的课后习题，检查学生对递归算法的掌握程度。
递归 课程设计一、课程目标知识目标：1. 让学生理解递归的概念，掌握递归算法的基本原理和应用。
2. 学会运用递归解决实际问题，如求解数学问题、处理数据结构等。
3. 了解递归在计算机科学中的重要性和局限性。
技能目标：1. 培养学生独立设计递归算法的能力，提高编程实践操作技能。
2. 能够分析递归算法的时间复杂度和空间复杂度，并进行优化。
3. 学会运用递归思想解决实际问题，培养逻辑思维和问题解决能力。
情感态度价值观目标：1. 激发学生对递归算法的兴趣，培养学习计算机科学的热情。
2. 培养学生的团队协作意识，学会在合作中共同解决问题。
3. 引导学生认识到递归在现实生活中的应用价值，提高对计算机科学的认识和认同。
课程性质：本课程为计算机科学相关学科的基础课程，旨在让学生掌握递归思想及其在实际问题中的应用。
学生特点：学生处于具备一定编程基础和逻辑思维能力的高年级阶段，对复杂问题有一定的分析解决能力。
教学要求：结合课本内容和实际案例，注重理论与实践相结合，强调学生的动手实践和团队协作能力培养。
通过本课程的学习，使学生能够熟练运用递归算法解决实际问题，并为后续相关课程打下坚实基础。
二、教学内容1. 递归概念与原理：介绍递归的定义、基本原理以及递归函数的构成要素。
- 课本章节：第三章第三节- 内容：递归定义、递归调用、递归条件、递归与循环的关系2. 递归算法设计与应用：讲解如何设计递归算法，分析递归算法的应用场景。
- 课本章节：第三章第四节- 内容：递归算法设计方法、递归算法应用实例、递归算法的优缺点3. 递归算法实践：通过实例讲解递归算法在实际编程中的应用。
- 课本章节：第三章第五节- 内容：递归求解数学问题、递归处理数据结构、递归优化4. 递归算法复杂度分析：分析递归算法的时间复杂度和空间复杂度，并进行优化。
- 课本章节：第三章第六节- 内容：递归算法复杂度概念、递归复杂度分析方法、递归优化策略5. 递归思想在实际问题中的应用：探讨递归思想在计算机科学及其他领域的应用。
2019-2020年高中信息技术递归算法的实现教案粤教版选修1一、教材分析“递归算法与递归程序”是广东教育出版社《算法与程序设计》选修1第四单元第五节的内容，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序，且在第二章中学习了自定义过程与函数。
在前面学习的基础上，学习递归算法的程序实现是自定义函数的具体应用，在培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。
二、学情分析教学对象是高中二年级学生，前面学习了程序设计的各种结构与自定义函数（过程）及常用基础算法，在学习程序设计各种结构的应用过程中，培养了学生用计算机编程解决现实中的问题的能力。
在学习循环语句的过程中，应用了大量的“递推”算法，在第二章中，学习了如何使用自定义函数，在此基础上深入学习和体会自定义函数的应用，以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。
多维度的思考问题和解决问题是提高学生的学习兴趣关键。
三、教学目标知识与技能：1、理解什么是递归算法，学会递归算法的思想分析问题2、能够应用递归算法编程处理实际问题过程与方法：学生参与讨论，通过思考、动手操作，体验递归算法的方法情感态度与价值：结合数学中的实例，激发学生使用数学知识建模的意识，培养学生多维度的思考问题和解决问题。
四、教学重点与难点重点：理解什么是递归算法难点：学生用递归算法的思想分析问题五、教学过程进程教师活动学生活动设计意图创设情境课堂导入：师：今天我们先做一个小的智力题目有4个人排成一队，问最后一个人的身高时，他说比第3个人高2厘米；问第3个人的身高时，他说比第2个人高2厘米；问第2个人的身高时，他说比第1个人高2厘米；最后问第1个人的身高，他师生共同活动找出递变规律使用情境教学法在此活动过程中能让学生初步从活动中体验“问题的发与收”从而走进了递归的思维模式，为说是170厘米，请问：第4个人的身高是多少？学生：176厘米师：如何得出的呢？结论：H4=H3+2=（H2+2）+2=（（H1+2）+2）+2 Hn=H(n-1)+2H1=176厘米H4 176=H3+2H3 174=H2+2H2 172=H1+2H1=170 并将算法描述进一步学习递归算法埋下伏笔学习新知任务1上台阶:10级台阶每次可上1级或2级，有多少种上法?基本情况描述1级台阶 1 1种2级台阶1+1 ，2 2种3级台阶1+1+1，1+2，2+1 3种………………10级台阶？分析：如何使问题简单化，若对第一步进行分析，则有两种情况：假设第一步上1级，则余n-1级。
递归课程设计一、教学目标本章节的教学目标是使学生掌握递归的基本概念、算法和应用，能够运用递归解决实际问题。
具体目标如下：1.知识目标：–了解递归的定义、分类和特点。
–掌握递归算法的实现和分析方法。
–熟悉常见的递归算法及其应用场景。
2.技能目标：–能够运用递归算法解决简单的问题，如递归求解 Fibonacci 数列、递归排序算法等。
–能够分析递归算法的时间和空间复杂度。
–能够运用递归思想设计和实现复杂问题的解决方案。
3.情感态度价值观目标：–培养学生的逻辑思维能力和解决问题的能力。
–培养学生对算法的兴趣和好奇心，激发学生深入学习计算机科学的热情。
–培养学生的团队合作意识和沟通能力，通过小组讨论和合作完成递归算法的实践项目。
二、教学内容本章节的教学内容主要包括递归的基本概念、算法和应用。
具体内容包括以下几个方面：1.递归的定义和分类：介绍递归的定义、特点和分类，如直接递归、间接递归和尾递归等。
2.递归算法的实现和分析：讲解递归算法的实现方法，如递归函数的定义和调用过程，以及递归算法的分析方法，如递归树的构建和时间复杂度的计算。
3.常见递归算法及其应用：介绍常见的递归算法，如递归求解Fibonacci 数列、递归排序算法等，并讲解它们在实际问题中的应用场景。
4.递归思想的应用：探讨递归思想在解决复杂问题中的应用，如分治算法、动态规划等。
三、教学方法为了激发学生的学习兴趣和主动性，本章节将采用多种教学方法相结合的方式进行教学。
具体方法如下：1.讲授法：通过讲解递归的基本概念、算法和应用，使学生掌握递归的基本知识和技巧。
2.案例分析法：通过分析具体的递归算法实例，使学生了解递归算法在实际问题中的应用。
3.小组讨论法：学生进行小组讨论，让学生分享自己的理解和思考，培养学生的团队合作意识和沟通能力。
4.实验法：安排学生进行递归算法的编程实验，让学生亲手实现和测试递归算法，提高学生的动手能力和解决问题的能力。
四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，我们将选择和准备以下教学资源：1.教材：选用权威、实用的递归算法教材，如《算法导论》、《计算机算法》等。
《递归算法与递归程序》教学设计一、教学目标1、知识与技能1）能够从思想和特点上理解什么是递归算法2）学会分析问题，能够建立合理的的递归数学模型3）能够自主设计递归函数解决实际问题2、过程与方法：1）通过分析身边的实例，理解递归算法的思想和特点2）通过通过层递的案例，理清递归法解决问题的过程3、情感态度与价值观：1）通过实际问题的解决，激发学生数学建模的意识和设计方法2）通过学习新的思维方式，培养学生多维度思考和解决问题的意识3）通过对递归算法解决问题的效率分析，使学生能更全面的认识和理解递归算法二、教学重点与难点1、教学重点1）理解什么是递归算法2）能够建立合理的的递归数学模型3）能够设计递归函数解决实际问题2、教学难点：1）能够建立合理的的递归数学模型2）能够设计递归函数解决实际问题三、教学方法主要采用讲授法、演示法、案例分析法、任务驱动法。
四、教学过程1、让学生演示常用报数方式。
引导学生分析得出答案的过程。
引出递推思想。
2、让学生演示一种另类的报数方式。
引导学生分析得出答案的过程。
引出递归思想。
递归法，相对于学生来说是比较抽象的，通过学生的两种演示、分析，能让学生从感性上对递归思想有一个形象的认识，从而能够更好的展开本节课的学习。
（或过程）倾听、分析思考通过展示递归定义，让学生从概念s as As 该案例与报数游戏思路完全一致，学生很容易找出关系式，建立数学模型。
通过进一步分析递归函数，让学生理解什么是自身调用自身？什么是递和归？通过案例1的学习分析，了解了递归思想，进而以归纳的方式展示递归思想的内涵，有助于学生更好的把握递归思想。
《递归算法与递归程序》教学设计
一、教学目标
1、知识与技能
1）能够从思想和特点上理解什么是递归算法
2）学会分析问题，能够建立合理的的递归数学模型
3）能够自主设计递归函数解决实际问题
2、过程与方法：
1）通过分析身边的实例，理解递归算法的思想和特点
2）通过通过层递的案例，理清递归法解决问题的过程
3、情感态度与价值观：
1）通过实际问题的解决，激发学生数学建模的意识和设计方法
2）通过学习新的思维方式，培养学生多维度思考和解决问题的意识3）通过对递归算法解决问题的效率分析，使学生能更全面的认识和理解递归算法
二、教学重点与难点
1、教学重点
1）理解什么是递归算法
2）能够建立合理的的递归数学模型
3）能够设计递归函数解决实际问题
2、教学难点：
1）能够建立合理的的递归数学模型
2）能够设计递归函数解决实际问题
三、教学方法
主要采用讲授法、演示法、案例分析法、任务驱动法。
四、教学过程
的过程。
引出递归
该案例与报数游。
递归的教学设计教学设计：递归一、设计背景递归是计算机科学中的重要概念之一，也是常见编程语言的基本特性。
掌握递归的概念及其应用，对学生编程能力的提升和算法思维的培养具有重要意义。
本教学设计旨在通过生动的教学方式和实践操作，帮助学生理解什么是递归以及如何运用递归解决问题。
二、教学目标1. 理解递归的概念及其特点；2. 掌握递归的基本应用场景；3. 学会编写递归算法解决实际问题；4. 培养学生的逻辑思维能力和问题求解能力。
三、教学内容1. 什么是递归？- 引导学生思考“自我调用”这一概念，并与递归进行对比。
- 讲解递归的定义：“在定义（或描述）某事物的过程中又涉及该事物本身的定义（或描述）。
”- 提供生活中的例子，如镜中嵌镜、星体间的引力、盘子的叠加等，加深学生对递归的理解。
2. 递归的特点- 介绍递归的三个基本要素：基线条件、递归条件和递归调用。
- 引导学生分析递归问题的关键点在于如何找到合适的基线条件和递归条件。
3. 递归的应用场景- 提供一系列例子，如斐波那契数列、阶乘计算、二叉树遍历等，让学生理解递归的常见应用场景。
- 强调递归能够简化代码逻辑、提高代码的可重用性和可读性。
4. 编写递归算法- 先从简单的例子入手，如编写一个递归函数计算斐波那契数列的第n个数，让学生掌握递归算法的基本写法。
- 通过实践操作让学生熟悉递归的编程过程，提供一系列习题供学生练习。
四、教学方法与过程1. 导入课程内容- 提出问题：你们知道什么是递归吗？递归在生活中有哪些应用？- 引导学生思考，开展小组讨论并进行汇报。
- 引入递归的定义和概念，给出递归的一些基本例子。
2. 讲解递归的特点和基本要素- 指导学生分析递归问题的关键点，强调基线条件和递归条件的重要性。
- 通过给出具体问题进行分析，加深学生对递归的理解。
3. 呈现递归的应用场景- 以斐波那契数列为例，讲解递归的实际应用。
- 带领学生探索递归的其他应用场景，并引导学生思考如何运用递归解决问题。
《递归算法》教学设计蚌埠新城实验学校徐田柱一、教学三维目标知识与技能：1、理解什么是递归算法，学生用递归算法的思想分析问题、解决问题2、能够应用自定义函数方法实现递归算法的编程过程与方法：学生参与讨论，通过思考、动手操作，掌握递归算法情感态度与价值：结合数学中的实例，激发学生的数学建模的意识，培养学生多维度的思考问题和解决问题。
二、教学重点与难点重点：理解什么是递归算法，学生用递归算法的思想分析问题、解决问题应用自定义函数方法实现递归算法的编程难点：应用自定义函数方法实现递归算法的编程三、教学策略教递归算法的实现思想是比较抽象，比较理论化的教学内容。
本着培养学生的发现问题、分析问题、解决问题的意识与能力入手。
知识主要是靠学生学会的，学习就是发生在学生头脑的建构。
因此，教师必须明确学生是学习的主体，研究学生学习的真实心理活动，分析其认识过程、机制及心智变化。
确定教学方法。
四、教学环境网络教室，教学软件DEV C++，大屏幕投影；五、教学资源准备从本学科的特点、学生的认知水平及学习心理特征，更好的激发学生的学习动机与信心，为保持学生的学习激情，设计了一系列难度层层递进的例题和练习。
六、教学过程（一）情景导入,提出课题师：从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚在讲故事，他讲的故事是：从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚在讲故事……师：这个故事体现了我们以前提到过的哪种程序设计算法？生：递归算法师：是的，引入课题，本节课我们就来深入学习递归算法。
设计意图：用故事引入课题，便于学生理解。
（二）新课探究，导出递归算法程序设计思想（1）例题1：求：f(n)=1+2+3+·(n-1)+n学生很容易想到以前学过的迭代算法：s=0;For(i=1;i<=n;i++) s=s+i;老师提出递归表达式：⎩⎨⎧>-+==时当时当 1 )1( 1 1n f n n n f(n)递归算法：long f(int n){if (n==1) return 1;else return n+f(n-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)可表示为：展示一般递归函数定义方法：程序测试效果def fac(n):if n == 0:s=1else:s= n * fac(n-1)return sprint(fac(3))6描述递归过程：设计意图：递归是程序设计里面比较高级的技术。
递归函数的定义比较特殊，它基于自己定义自己。
初学者感觉困对应地，可以跟踪递归函数中参数n 的变化情况： 程序 测试效果def fac(n): if n == 0: s=1 else: print(str(n)+'*fac('+str(n-1)+')') s= n * fac(n-1) return s print(fac(3)) 3*fac(2)2*fac(1)1*fac(0)6设问：前面，我们已经学习过斐波那契数列的递推公式：a 1 = 1a 2 = 1a n =a n-1+a n-2(当n>2时)你能编写对应的递归程序由计算机计算一年后的兔子总数吗？参考程序：Fibonacci 程序递归算法：def fib(n ):if n == 1 or n == 2:return 1else :return fib(n - 1) + fib(n - 2)print("到12月共有%d 只兔子." % (fib(12)))教师总结：能采用递归描述的算法通常有这样的特征：为求解规模为N 的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法。
递归入门教案（3课时）常州外国语学校朱春华一、教材分析递归算法作为一种基本算法，在计算机程序设计中具有非常重要的作用。
本节课紧跟在“自定义函数和过程”这一内容的后面，在详细阐述了主程序对子程序的调用以及子程序对子程序的调用的基础上展开。
循序渐进地引入递归算法，旨在培养学生“自顶向下”、“逐步求精”的程序设计思想。
二、学情分析教学对象是编程兴趣班的学生，以小学高年级和初一学生为主，前面学习了程序设计的各种结构，并已能灵活应用这些知识用计算机编程解决现实中的部分问题。
通过自定义函数和过程这两种子程序的学习，同学们已初步建立了结构化设计的思想，能熟练地在主程序中调用子程序或在子程序中调用另一子程序。
子程序自己调用自己的思想也能为学生所接受，但调用会产生什么后果学生不了解，这正是递归的难点。
子程序自己调用自己是如何进行的，如何用计算机来实现？对于任何要解决的问题是否都可以使用递归算法？如何用递归算法来解决问题，这些都是学生急于知道的。
三、教学目标知识与技能：1、理解什么是递归算法，学会用递归算法的思想分析问题；2、能够编程使用自定义函数实现递归算法；3、能够编程使用自定义过程实现递归算法；过程与方法：通过体验递归算法的“递”与“归”的过程，了解递归算法的本质；通过对个别问题的讨论和抽象，让学生了解递归问题的普遍解决方法。
情感态度与价值：结合数学中的实例，激发学生的数学建模的意识，培养学生多维度的思考问题和解决问题。
四、教学重点与难点重点：理解递归算法的本质，了解使用递归算法解决问题的一般方法；编程使用自定义函数实现递归算法；编程使用自定义过程实现递归算法。
难点：具体问题递归方程式的建立。
五、教学方法：演练法、讨论法、比赛法。
六、教学过程教学反思从生活引例导入递归的概念，利用引例二调动学生的积极思考，通过对引例二中变量的全程跟踪让学生明白了递归的实现过程，并顺理成章地将这一用普通过程调用方式编写的程序改写成用递归来实现的程序。
《递归算法与递归程序》教学设计一、教学目标：1.了解递归算法的基本概念和原理；2.能够运用递归算法解决实际问题；3.掌握递归程序的编写方法；4.培养学生的逻辑思维能力和问题解决能力。
二、教学内容：1.递归算法的概念和原理；2.递归程序的编写方法；3.递归算法的应用。
三、教学重点：1.递归算法的基本概念和原理；2.递归程序的编写方法。
四、教学难点：1.理解递归算法的原理；2.掌握递归程序的编写方法。
五、教学准备：1.教学课件；2.计算机实验室。
六、教学过程：Step 1：导入新知识（5分钟）教师简要介绍递归算法的定义和原理，引起学生的兴趣。
Step 2：逐步讲解递归算法的实现过程（15分钟）1.首先，教师通过实例讲解递归算法的基本思想和实现过程。
例如，实现一个计算n的阶乘的递归函数；2.其次，教师演示如何通过递归实现斐波那契数列；Step 3：让学生进行小组讨论（10分钟）学生分成小组，互相讨论递归算法的应用场景，并提出问题。
Step 4：学生进行实践操作（20分钟）1.学生根据教师提供的案例，自行编写递归程序；2.学生互相交流和讨论，共同探索递归算法的应用。
Step 5：教师总结并展示优秀作品（10分钟）教师总结学生的实践情况，并邀请优秀作品进行展示和分享。
Step 6：课堂小结（5分钟）教师对本课内容进行总结，并提出问题，激发学生的思考。
七、教学方法：1.讲授法：通过课件和实例讲解递归算法的基本概念和原理；2.实践操作：让学生进行编程实践，培养实际操作能力；3.小组讨论：学生互相讨论，共同探索递归算法的应用；4.总结分享：教师总结学生实践情况，并邀请优秀作品进行分享。
八、教学评价：1.学生在编写递归程序时的操作是否规范、正确；2.学生在小组讨论中的参与度和提问能力；3.学生在实践操作和展示过程中的表现。
九、教学延伸：1.学生可以继续深入研究递归算法的应用场景，拓宽解决问题的思路；2.学生可以进一步优化递归程序，提高效率；3.学生可以继续学习其他高级算法，如动态规划等。
信息技术《递归法》教案一、教学目标1.能够说出递归法的含义和推导过程，并能在具体问题中利用递归思想写出程序代码。
2.通过自主探究和合作学习，提升用递归思想解决问题的能力。
3.通过利用递归法求身高的过程，学会利用递归法写出代码，激发学习程序设计的兴趣。
二、教学重难点【重点】递归法的含义和推导过程。
【难点】在VB中递归算法的实现。
三、教学过程(一)导入新课创设情景：有4个人排成一队，问最后一个人的身高时，他说比第3个人高2厘米;问第3个人的身高时，他说比第2个人高2厘米;问第2个人的身高时，他说比第1个人高2厘米;最后问第1个人的身高，他说是170厘米。
提出问题：如何去计算第4个人的身高呢?【利用第1个人身高，求出第2个人身高，并依次推算出第4个人身高】教师总结：像这种利用一个已知数一步步进行推算的方法，就是递归法。
递归法的具体过程又是怎样的呢?本节课就围绕递归法展开教学。
(二)新课讲授1.递归过程针对导入的情景，提出问题：(1)问题的出发点和已知条件分别是什么?【求第4个人身高和第1个人身高】(2)前后相邻两人在身高上有什么样的数量关系?【H4=H3+2，H3=H2+2，H2=H1+2，H1=170厘米】(3)根据第一个人的身高，如何求出第4个人的身高?【H1=170厘米，H2=H1+2=172厘米，H3=H2+2=174厘米，H4=H3+2=176厘米】教师总结：由求第4个人身高的问题转化为求第3个人身高的问题，最后到求第1个人身高的问题，该阶段为递推阶段。
从第1个人的已知身高推算出第2个人的身高，一直到推算出第4个人的身高的阶段为返回阶段。
递推阶段和返回阶段共同构成递归过程。
教师讲解用n表示第n个人，用函数H(n)表示第n个人的身高，提出问题：(1)递归的终止条件是什么?【问题的初始条件H(1)=170厘米】(2)H(n)和H(n-l)的关系是什么?【H(n)=H(n-l)+2】教师总结：递归法的实现有两部分组成，一是递归的终止条件;二是将原问题转化为与原问题相似的、更接近终止条件的新的问题。
递归算法与递归程序岳西中学：崔世义一、教学目标1知识与技能(1) •认识递归现象。
(2) •使用递归算法解决冋题往往能使算法的描述乘法而易于表达(3) •理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。
(4) •认识递归算法往往不是咼效的算法。
(5) • 了解递归现象的规律。
(6) •能够设计递归程序解决适用于递归解决的问题。
(7) •能够根据算法写出递归程序。
(8) • 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。
2、方法与过程本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。
然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。
最后用子过程解决汉诺塔的经典问题。
3、情感态度和价值观结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。
二、重点难点1、教学重点(1) 了解递归现象和递归算法的特点。
(2) 能够根据问题设计出恰当的递归程序。
2、教学难点(1) 递归过程思路的建立。
(2) 判断冋题是否适于递归解法。
(3) 正确写出递归程序。
三、教学环境1、教材处理教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。
然后利用子过程解决汉诺塔的经典问题。
教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。
然后让学生做练习⑵ 和练习⑶ 这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。
最后用子过程解决汉诺塔的经典问题。
教学方法采用讲解、探究、任务驱动和学生自主学习相结合2、预备知识学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。
四、教学过程导入：大家玩汉诺塔游戏：这个游戏盘子在A、B C三根柱子上不停运动，有没有规律，和你在照过镜子时遇到的情况相同吗？当你往镜子前面一站，镜子里面就有一个你的像。
但你试过两面镜子一起照吗？如果甲、乙两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”！为什么会有这么奇妙的现象呢？原来，甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。
这是一种递归现象。
由同学们总结出递归算法的概念递归算法：是一种直接或者间接地调用自身的算法。
在计算机编写程序中, 递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
问题4-16 :著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。
如果年初养了一对小兔子，问到年底时将有多少对兔子？(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)我们不难用以前学过的知识设计出如下算法：①输入计算兔子的月份数：n②If n < 3 The n c = 1 Else a = 1: b = 1③i = 3④c = a + b : a = b : b = c⑤i=i+1,如果i < n则返回④⑥结束参考程序如下：Private Sub Comma nd1_Click()n = Val(Text1.Text)If n < 3 The n c = 1 Else a = 1: b = 1For i = 3 To nc = a + ba = bb = cNext iText2.Text =" 第"& n & "月的兔子数目是："& c End Sub开动脑筋：我们有没有更简单的方法解决该问题呢？4.5.1 从斐波那契的兔子问题看递归算法1 •斐波那契的兔子问题子⑴分析冋题。
我们可以根据题意列出表4-3来解决这个问题: 表4—3兔子问题分析表这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。
(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一般的方法，去解决这个问题。
交流仔细研究表4-8，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？恭喜你，你快成功了？⑵设计算法。
“兔子问题”很容易列出一条递推式而得到解决。
假设第N个月的兔子数目是F(N)，我们有：这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。
由上述的递推式我们可以设计出递归程序。
递归程序的特点是独立写出一个函数(或子过程)，而这个函数只对极简单的几种情况直接给出解答，而在其余情况下通过反复的调用自身而把问题归结到最简单的情况而得到解答。
刖面学过：自定义函数的定义格式：Function 函数名(参数表)[As type]过程中的代码End Fun cti on调用函数的格式：函数名(参数表)(3) 编写程序。
窗体中开设一个文本框Textl用于填人月数N,设置命令框Commandl点击它即执行程序求出第N月的兔子数。
然后用文本框Text2输出答案。
根据递推式可以写出递归程序如下：Function Fib(ByVal N As Integer) As LongIf N < 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2) End Fun cti onPrivate Sub Comma nd1_Click()N = Val(Text1.Text)Text2.Text =" 第"& N & "月的兔子数目是："& Fib(N)End Sub⑷调试程序因为这个算法的效率不高，建议在调试程序时月份数不要大于40。
4.5.2 —个应用递归算法解决的问题经典例子问题4-17 :传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。
一名僧人把这些金盘从一根宝石柱移到另外一根上。
僧人在移动金盘时遵守下面3条规则：第一，一次只能移动一个金盘。
第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。
第三，任何时候都不能把大的金盘放在小的金盘上。
神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。
当然，神话只能当故事来听，世界不可以因为个别人的活动而导致末日。
不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！(1) 分析问题。
我们把3根宝石柱分别命名为A、B、C。
最初有N个金盘放在A,需要把它们全部按规则移动到Bo当N=1时，直接把金盘从A搬到B就可以了，1次成功。
当N A2,那么需要利用C柱来过渡。
我们假设已经找到一种把N—1个金盘从一根柱搬到另外一根柱的方法，那么，我们只要把N-1个金盘从A搬到C,然后把最大的金盘从A搬到B,最后把C上的N一一1个金盘搬到B就可以了。
靠递归的思想，我们轻而易举地完成了整个搬动。
⑵设计算法。
我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘需要从A柱搬到B 柱(以C柱为过渡)。
那么完成它只需3步：①Hanoi(N —1, A，C, B)它的意思是把A柱上的N —1个金盘搬到C柱;②A-B它的意思是把一个(最大的)金盘从A柱搬到B柱；③Hanoi(N —1, C, B, A)它的意思是把c柱上的N —1个金盘搬到B柱。
前面已经学过：过程定义的格式：Private Sub 过程名(参数表)代码End Sub调用过程的格式：Call过程名(参数表)(3)编写程序(引导学生编写程序)。
Private Sub Hanoi(n As Integer, ByVai A As String, ByVai B As String, ByVai C As Stri ng, t As Long)If n = 1 The n Text3.Text = Text3.Text + A + " —" + B + vbCrLft = t + 1 '增加变量t用来统计移动次数。
ElseCall Hanoi(n - 1, A, C, B, t)Text3.Text = Text3.Text + A + " t = t + 1Call Hanoi(n - 1, C, B, A, t) End If End SubPrivate Sub Comma nd1_Click() Dim t As Long, n As In teger t = 0 n = Val(Text1.Text) A = "A" B = "B"Call Hanoi(n, A, B, C, t) Text2.Text = t End Sub⑷测试程序 在文本框中输入4。
小结：递归算法的特点递归过程一般通过函数或子过程来实现。
递归算法：在函数或子过程的内部，直接或者间接地调用自己的 算法。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。
然后递归调 用函数(或过程)来表示问题的解。
递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。
(2) 在使用递增归策略时，必须有一个明确的 递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
所以一般 不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归次数过多容易造成栈溢出等。
所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备 (通常前一次的 输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行 递归调用，因而每次递 归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将 会成为死循环而不能正常结束。
