递归算法与递归程序.ppt

《递归算法与递归程序.ppt》由会员分享，可在线阅读，更多相关《递归算法与递归程序.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归算法与递归程序递归算法与递归程序(第一课时第一课时)湛江师范学院附属中学湛江师范学院附属中学 韦东韦东 教学目标教学目标 (1)(1)(1)(1)、知识目标、知识目标、知识目标、知识目标 认识递归现象；认识递归现象；认识递归现象；认识递归现象；认识递归算法的优缺点；认识递归算法的优缺点；认识递归算法的优缺点；认识递归算法的优缺点；了解递归算法的特点；了解递归算法的特点；了解递归算法的特点；了解递归算法的特点；理解递归三要素。理解递归三要素。理解递归三要素。理解递归三要素。(2)(2)(2)(2)、能力目标、能力目标、能力目标、能力目标 能够分析递归问题并设计算法；能够分析递归问题并设计算法

2、；能够分析递归问题并设计算法；能够分析递归问题并设计算法；能够根据算法写出递归程序。能够根据算法写出递归程序。能够根据算法写出递归程序。能够根据算法写出递归程序。(3)(3)(3)(3)、情感态度与价值观、情感态度与价值观、情感态度与价值观、情感态度与价值观 了解生活中的递归现象，领悟递归现象的既有重复，又有了解生活中的递归现象，领悟递归现象的既有重复，又有了解生活中的递归现象，领悟递归现象的既有重复，又有了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法，并通过问题变化的特点，并且从中学习解决问题的一种方法，并通过问题变化的特点，并且从中学习解决问题

3、的一种方法，并通过问题变化的特点，并且从中学习解决问题的一种方法，并通过问题的解决，体验成就感，增强学习兴趣。的解决，体验成就感，增强学习兴趣。的解决，体验成就感，增强学习兴趣。的解决，体验成就感，增强学习兴趣。观察实验：双镜成像观察实验：双镜成像镜中的像有何规律和特点。镜中的像有何规律和特点。镜中的像有何规律和特点。镜中的像有何规律和特点。影子一个比一个小；影子一个比一个小；影子一个比一个小；影子一个比一个小；第一个影子由实物得到，第一个影子由实物得到，第一个影子由实物得到，第一个影子由实物得到，然后每一个影子都是上一然后每一个影子都是上一然后每一个影子都是上一然后每一个影子都是上一个的像；

4、个的像；个的像；个的像；影子有无限个。影子有无限个。影子有无限个。影子有无限个。任任务务解决斐波那契兔子问题解决斐波那契兔子问题：（按小组进行讨论分析）：（按小组进行讨论分析）1、算法分析：、算法分析：（1）说出人工列表解法的缺点：）说出人工列表解法的缺点：（2）如何确立递归分析思路：）如何确立递归分析思路：2、程序设计：、程序设计：（1）如何用程序反映算法）如何用程序反映算法，你能总结其一般步骤如何吗？，你能总结其一般步骤如何吗？（2）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？3、实践应用：、实践应用：分组实践练习分组实

5、践练习，课本，课本137页练习页练习2、3，并比较算法与程序设计代码，并比较算法与程序设计代码 任任务务解决斐波那契兔子问题解决斐波那契兔子问题：（按小组进行讨论分析）：（按小组进行讨论分析）1、算法分析：、算法分析：（1）说出人工列表解法的缺点：）说出人工列表解法的缺点：慢，效率低慢，效率低（2）如何确立递归分析思路：）如何确立递归分析思路：寻找数据规律，能否将复杂的处理归纳为较简单的处理，直到最简寻找数据规律，能否将复杂的处理归纳为较简单的处理，直到最简单的处理。单的处理。形成递归算法：形成递归算法：递归的形式递归的形式:F（N）=F（N-1）+F（N-2）N3 终止的条件和最基本式是否有

6、直接解决终止的条件和最基本式是否有直接解决:F（1）=F（2）=1任任务务解决斐波那契兔子问题解决斐波那契兔子问题：（按小组进行讨论分析）：（按小组进行讨论分析）2、程序设计：、程序设计：（1）如何用程序反映算法）如何用程序反映算法，你能总结其一般步骤如何吗？，你能总结其一般步骤如何吗？界面设计；界面设计；定义递归函数（过程）定义递归函数（过程）应用应用(调用调用)函数；函数；（2）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？）非递归算法的效率分析，你能就原设计界面不变而修改代码吗？Private Sub Command1_Click()Text2.Text=N=Val(Text1

7、.Text)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 Text2.Text=第第&N&月的兔子数目是：月的兔子数目是：&cEnd Sub 递归程序简洁明了，易于理解，可读性强，效率较低。非递归程序设计需要递归程序简洁明了，易于理解，可读性强，效率较低。非递归程序设计需要较强的程序设计的经验，效率较高。较强的程序设计的经验，效率较高。任任务务解决斐波那契兔子问题解决斐波那契兔子问题：（按小组进行讨论分析）：（按小组进行讨论分析）3、实践应用：、实践应用：分组实践练习分组实践练习，课本，课本137页练

8、习页练习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)N2。又显然最基本式为：。又显然最基本式为：F(1)=1，F(2)=2。程序如下：。程序如下：Function F(ByV

9、al n As Integer)As Long If n=2 Then F=n Else F=F(n-1)+F(n-2)End FunctionPrivate 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级楼梯。当第级楼梯

10、。当第一步为一步为1级时剩下楼梯的级数为级时剩下楼梯的级数为N-1，故，故方法数为方法数为F(N-1)；当第一步为；当第一步为2级时，剩级时，剩下楼梯的级数为下楼梯的级数为N-2，故方法数为，故方法数为F(N-2)。于是递归形式为于是递归形式为F(N)=F(N-1)+F(N-2)N2。又显然最基本式为。又显然最基本式为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 FunctionPrivate Sub Form_Click()Dim n

11、 As Integer n=Val(InputBox(请输入楼梯级数请输入楼梯级数N：,输入楼梯级数输入楼梯级数)Print 当楼梯级数当楼梯级数;n;时时,Print 可以有可以有;F(n);种不同的上楼种不同的上楼梯方法。梯方法。End Sub 递归算法的特点：递归算法的特点：1、递归算法实际有否直接找到解决办法？、递归算法实际有否直接找到解决办法？2、递归算法的实质是把问题转化为规模缩小了的同类问题的子问题。、递归算法的实质是把问题转化为规模缩小了的同类问题的子问题。3、要实现递归算法，应当具备什么要求：、要实现递归算法，应当具备什么要求：每次调用在规模上都有所缩小；每次调用在规模上都有

12、所缩小；相邻两次重复之间有紧密的联系，前一次要为后一次做准备；相邻两次重复之间有紧密的联系，前一次要为后一次做准备；在问题的规模极小时必须用直接给出解答而不再进行递归调用。在问题的规模极小时必须用直接给出解答而不再进行递归调用。1、概念：递归算法就是一种直接或者间接地调用自身的算法。、概念：递归算法就是一种直接或者间接地调用自身的算法。2、问题解决：斐波那契兔子问题。、问题解决：斐波那契兔子问题。(1)确立递归思路：确立递归思路：寻找数据规律寻找数据规律,能否将复杂的处理归纳为较简单的处理能否将复杂的处理归纳为较简单的处理,直到最简单的处理。直到最简单的处理。形成递归算法：形成递归算法：递归的

13、形式：递归的形式：F（N）=F（N-1）+F（N-2）N3终止的条件和最基本式是否有直接解决：终止的条件和最基本式是否有直接解决：F（1）=F（2）=1(2)用程序反映算法。用程序反映算法。界面设计界面设计定义递归函数（过程）定义递归函数（过程）应用应用(调用调用)函数函数3、递归与非递归效率的比较。、递归与非递归效率的比较。递归程序简洁明了，易于理解，可读性强，一般效率较低。非递归程序设计递归程序简洁明了，易于理解，可读性强，一般效率较低。非递归程序设计需要较强的程序设计的经验，效率较高。需要较强的程序设计的经验，效率较高。4、递归算法的实质是把问题转化为规模缩小了的同类问题的子问题。、递归

14、算法的实质是把问题转化为规模缩小了的同类问题的子问题。5、实现递归算法应具备的要求：、实现递归算法应具备的要求：每次调用在规模上都有所缩小；每次调用在规模上都有所缩小；相邻两次重复之间有紧密的联系，前一次要为后一次做准备；相邻两次重复之间有紧密的联系，前一次要为后一次做准备；是在问题的规模极小时必须用直接给出解答而不再进行递归调用。是在问题的规模极小时必须用直接给出解答而不再进行递归调用。知识小结知识小结知识小结知识小结 作业：作业：1、完善刚才练习、完善刚才练习2、3的界面设计，使能有具的界面设计，使能有具体的输入界面和输出界面。体的输入界面和输出界面。2、练习、练习1的算法分析及代码设计；

15、的算法分析及代码设计；3、预习下一课（即本节内容第二部分）：、预习下一课（即本节内容第二部分）：（1）如何理解汉诺塔问题中的算法；）如何理解汉诺塔问题中的算法；（2）如何编程好的界面的程序；）如何编程好的界面的程序；（3）应用递归的特点。）应用递归的特点。拓展拓展 知识知识通过浏览校园内网网页，了解：通过浏览校园内网网页，了解：1、递归算法解题的一般思路递归算法解题的一般思路；2、递归向非递归的转化知识递归向非递归的转化知识；3、斐波那契螺旋斐波那契螺旋。界面设计界面设计:输入文本框控件输入文本框控件 输出文本框控件输出文本框控件 运算命令按钮运算命令按钮 文字标签控件文字标签控件 定义递归函数（过程）定义递归函数（过程）Function Fib(ByVal N As Integer)As Long If N 3 Then Fib=1 Else Fib=Fib(N-1)+Fib(N-2)End Function应用应用(调用调用)函数函数Private Sub Command1_Click()Text2.Text=N=Val(Text1.Text)Text2.Text=第&N&月的兔子数目是：&Fib(N)End Sub