高中信息技术选修1教案-4.5 递归算法与递归程序-粤教版

《递归算法与递归程序》
一、教材分析
　　“递归算法与递归程序”是广东教育出版社《算法与程序设计》选修1第四单元第五节的内容，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序，且在第二章中学习了自定义过程与函数。在前面学习的基础上，学习递归算法的程序实现是自定义函数的具体应用，在培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。
　　二、学情分析
　　教学对象是高中二年级学生，前面学习了程序设计的各种结构与自定义函数（过程）及常用基础算法，在学习程序设计各种结构的应用过程中，培养了学生用计算机编程解决现实中的问题的能力。在学习循环语句的过程中，应用了大量的“递推”算法，在第二章中，学习了如何使用自定义函数，在此基础上深入学习和体会自定义函数的应用，以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。
　　三、教学目标
　　知识与技能：
　　1、理解什么是递归算法，学会递归算法的思想分析问题
　　2、能够应用函数递归算法编程处理实际问题
　　过程与方法：学生参与讨论，通过思考、动手操作，体验递归算法的方法
情感态度与价值：结合数学中的实例，激发学生使用数学知识建模的意识，培养学生多维度的思考问题和解决问题。
四、教学重点与难点
　　重点：理解什么是递归算法
难点：学生用函数解决问题的递归算法的思想分析问题
五、教学过程：
进程
教师活动
学生活动
设计意图
创设情境
课堂导入：
什么是递归法？
趣味故事：
很久以前，有一则古老而有趣的故事流传至今：
从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲什么呢？
从前有座山，山里有座庙，……
这个故事中蕴含了递归思想！
游戏：老师的手里拿了一个东西，只有一个学生知道，每个学生只能问一次，也只能作一次回答，最后直到一位同学问到正确答案结束。
这个游戏中也蕴含了递归思想！
?
?
?
?
师生共同活动找出递变规律
并将算法描述
使用情境教学法
在此活动过程中能让学生初步从活动中体验“问题的发与收”从而走进了递归的思维模式，为进一步学习递归算法埋下伏笔
学习新知
学习任务
1.递归法的概念：
如果一个函数在定义时，直接或间接地调用了自己，这种算法在程序设计中统称为递归法。
2.递归法包括2种情况：
※函数自己调用自己
※两个函数之间相互调用
3.函数的概念：
函数是为了实现某种功能而编写的一段相对独立的程序。
函数的种类：
标准函数：abs（）、len（）、mid（）、chr（）、asc（）……
自定义函数：是指我们自己编写的函数。
在VB中，自定义函数形式如下：
[Public|Private] Function <函数名称> ([参数列表]) [As 类型]
局部常量、变量定义
语句组
函数名称=返回值
End Function
例子：
Public Function s(n As Integer) As Long
If n = 1 Then
s =1
Else
s =s(n-1)*n
End If
End Function

自定义函数的调用，可以有三种格式：
变量=函数名称（参数）
Call 函数名称（参数）
函数名称 参数
子过程的定义：
[public|private] sub <子过程名称> ([参数列表])
局部常量、变量定义
过程语句组
End sub
例子：
private sub s(n As Integer) As Long
If n = 1 Then
s =1
Else
s =s(n-1)*n
End If
End sub
应用举例：比较两个数的大小
Public Function max(n As Integer) As Integer
If a>b Then
max=a
Else
max=b
End If
End Function
Private Sub command_Click() ' 调用递归函数，显示结果
Print max(3,5)
End Sub
递归的基本思想：
把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定的程度直到可以直接得出它的解，从而得到原来问题的解。
讨论、比较、分析、归纳
?
?
?
?
?
?
?
?
?
?
?
?
?用数据方法推导解决过程，建立解决问题的数学模型（建模）
实例教学。
选择多个实际问题，使用常规方法（通常用枚举方法）分析与解决较为复杂，但使用递归方法，问题可以轻松解决，从使得重点难点得以轻松的突破。
??
?
??
?
课堂小结
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
(1)??? 递归就是在过程或函数里调用自身。
(2)??? 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3)??? 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序
注意：必须要有一个结束递归的条件，不得无限递归。
分析步骤：
1）.决定问题规模的参数。
2）.问题的边界条件及边界值。
3）.解决问题的通式。
例:计算一个数的阶乘
1!=1 f(1)=1
2!=1*2 f(2)=f(1)*2
3!=1*2*3 f(3)=f(2)*3
4!=1*2*3*4 f(4)=f(3)*4
5!=1*2*3*4*5 f(5)=f(4)*5
……. ……..
n!=1*2*3*4*5*….*n f(n)=f(n-1)*n
实例：vb程序求5！结果：
Public Function s(n As Integer) As Long
If n = 1 Then
s =1
Else
s =s(n-1)*n
End If
End Function
Private Sub form_Click() ' 调用递归函数，显示结果
Print "s(5)="; s(5)
End Sub
实例：有人养了一对兔子，这对兔子以后每月生一对兔子，新生兔子从第三个月开始，也是每月生一对兔子，问12个月后这人有多少对新生兔子？
用递归法实现。参考代码如下：
Public Function S(N As Integer) As Integer
If N = 1 Or N= 2 Then
S = 1
Else
S = S(N－1) + S(N－2)
End If
End Function
实例：年龄问题
有5个人做在一起，问第5个人多大了。他说比第四个人大2岁，问第四个人多大了，他说比第三个人大2岁，问第三个人多大了，他说比第二个人大2岁，问第二个人多大了，他说比第一个人大2岁，最后问第一个人，他说他10岁了。请问第5个人多大了？
总结：
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
(1)??? 递归就是在过程或函数里调用自身。
(2)??? 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3)??? 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序
巩固和发展本节课的学习内容。
拓展资源
主题网站