(
课件网) 递 归 算 法 什么是递归算法 递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 斐波那契的兔子问题 某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。 分析: 第一个月是最初的一对兔子生下一对兔子，围墙内共有两对兔子。第二个月仍是最初的一对兔子生下一对兔子，共有3对兔子。到第三个月除最初的兔子新生一对兔子外，第一个月生的兔子也开始生兔子，因此共有5对兔子。继续推下去，第12个月时最终共有对377对兔子。每个月的兔子总数可由前两个月的兔子数相加而得。 算法: ① 输入计算兔子的月份数：n ② If n < 3 Then c = 1 Else a = 1: b = 1 ③ i = 3 ④ c = a + b：a = b：b = c ⑤ i=i+1,如果i≤n则返回④ ⑥ 结束 Private Sub Command1_Click() n = Val(Text1.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 Text2.Text = "第" & n & "月的兔子数目是：" & c End Sub 开动脑筋： 我们有没有更简单的方法解决该问题呢？ (1)分析问题 我们可以根据题意列出表来解决这个问题： 兔子问题分析表 交流: 仔细研究兔子问题分析表，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？ (2)设计算法。 “兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有： 这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。 由上述的递推式我们可以设计出递归程序。递归程序的特点是独立写出一个函数(或子过程)，而这个函数只对极简单的几种情况直接给出解答，而在其余情况下通过反复的调用自身而把问题归结到最简单的情况而得到解答。 知识复习： 自定义函数的定义格式: Function procedurename(arguments) [As type] Statements End Function 其中的procedurename是函数名，arguments是函数中的参数表，type是函数返回值的数据类型，[]表示可有可无的部分，statements是过程中的代码 调用函数的格式： procedurename(arguments) (3)编写程序 窗体中开设一个文本框Text1用于填人月数N，设置命令框Commandl，点击它即执行程序求出第N月的兔子数。然后用文本框Text2输出答案。 根据递推式可以写出递归程序如下： 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() N = Val(Text1.Text) Text2.Text = "第" & N & "月的兔子数目是：" & Fib(N) End Sub (4)调试程序 因为这个算法的效率不高，建议在调试程序时月份数不要大于40。 知识迁移： (1)利用递归方法编写一求N的阶乘。 分析： 根据N!=N*(N-1)*(N-2)*(N-3)*……*3*2*1 可以推出下列式子： Function F(ByVal n As Integer) As Long If n = 1 Then F = 1 Else F = n * F(n - 1) End Function Private Sub Form_Click() Dim n As Integer n = Val(InputBox("请输入正整数N：", "求N的阶乘")) Print " 输入的正整数是"; n; Print "，阶乘是"; F(n) End Sub 本节小结： 递归算法的特点 递归过程一般通过函数或子过程来实现。 递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。 递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。 递归算法解决问题的特 ... ...
