算法与程序5.5递归算法

(共20张PPT)
递 归 算 法
什么是递归算法
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
斐波那契的兔子问题
某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问一年后围墙中共有多少对兔子。
分析:
第一个月是最初的一对兔子生下一对兔子，围墙内共有两对兔子。第二个月仍是最初的一对兔子生下一对兔子，共有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
本节小结：
递归算法的特点
递归过程一般通过函数或子过程来实现。
递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。