递归算法与递归程序.ppt

递归算法与递归程序
(第一课时)
湛江师范学院附属中学 韦东
教学目标
(1)、知识目标
①认识递归现象；
②认识递归算法的优缺点；
③了解递归算法的特点；
④理解递归三要素。
(2)、能力目标
①能够分析递归问题并设计算法；
②能够根据算法写出递归程序。
(3)、情感态度与价值观
了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学****解决问题的一种方法，并通过问题的解决，体验成就感，增强学****兴趣。
观察实验：双镜成像
镜中的像有何规律和特点。
①影子一个比一个小；
②第一个影子由实物得到，然后每一个影子都是上一个的像；
③影子有无限个。
任务
解决斐波那契兔子问题 ：（按小组进行讨论分析）
1、算法分析：
（1）说出人工列表解法的缺点：
（2）如何确立递归分析思路：
2、程序设计：
（1）如何用程序反映算法 ，你能总结其一般步骤如何吗？
（2）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？
3、实践应用：
分组实践练****课本137页练****2、3 ，并比较算法与程序设计代码
任务
解决斐波那契兔子问题 ：（按小组进行讨论分析）
1、算法分析：
（1）说出人工列表解法的缺点：
慢，效率低
（2）如何确立递归分析思路：
①寻找数据规律，能否将复杂的处理归纳为较简单的处理，直到最简单的处理。
②形成递归算法：
递归的形式:F（N）=F（N-1）+F（N-2） N≥3
终止的条件和最基本式是否有直接解决:F（1）=F（2）=1
任务
解决斐波那契兔子问题 ：（按小组进行讨论分析）
2、程序设计：
（1）如何用程序反映算法 ，你能总结其一般步骤如何吗？
①界面设计；
②定义递归函数（过程）
③应用(调用)函数；
（2）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？
Private Sub Command1_Click()
= ""
N = Val()
If N < 3 Then
c = 1
Else
a = 1: b = 1
For i = 3 To N
c = a + b: a = b: b = c
Next i
End If
= "第" & N & "月的兔子数目是：" & c
End Sub
递归程序简洁明了，易于理解，可读性强，效率较低。非递归程序设计需要较强的程序设计的经验，效率较高。
任务
解决斐波那契兔子问题 ：（按小组进行讨论分析）
3、实践应用：
分组实践练****课本137页练****2、3 ，并比较算法与程序设计代码
(2)假设和为N时可列式子的方法数是F(N)，那么第一个加数可选择1或2。当第一个加数为1时剩下加数的和为N-1，故方法数为F(N-1)；当第一个加数为2时，剩下加数的和为N-2，故方法数为F(N-2)。于是递归形式为：F(N)=F(N-1)+F(N-2) N≤2。又显然最基本式为：F(1)=1，F(2)=2。程序如下：
Function F(ByVal n As Integer) As Long
If n <= 2 Then F = n Else F = F(n - 1) + F(n - 2)
End Function
Private Sub Form_Click()
Dim n As Integer
n = Val(InputBox("请输入正整数N：", "输入式子的总和"))
Print "当总和是"; n; "时,"
Print "可以列出不同的由1和2组成的加法式子"; F(n); "条。"
End Sub
(3)假设楼梯级数为N时的方法数是F(N)，那么第一步可选择1或2级楼梯。当第一步为1级时剩下楼梯的级数为N-1，故方法数为F(N-1)；当第一步为2级时，剩下楼梯的级数为N-2，故方法数为F(N-2)。于是递归形式为F(N)=F(N-1)+F(N-2) N≤2 。又显然最基本式为F(1)=1，F(2)=2。程序如下：
Function F(ByVal n As Integer) As Long
If n <= 2 Then F = n Else F = F(n - 1) + F(n