分析思考：尝 试用递归思想 设计数学模型
案例1递归函数：
Function s (byval n as integer) As Integer If n=1 then
s=10 else
s=s(n-1)+2 end if End function
2：递归思想的内涵：
有去有回才是递归。 递归问题必须可以分解为若干个规模较小，与原问题形式相同的
(1)分析问题
• 我们把3根宝石柱分别命名为A、B、C。最初有N个金盘放在A， 需要把它们全部按规则移动到B。当N=1时，直接把金盘从A搬 到B就可以了，1次成功。当N≥2，那么需要利用C柱来过渡。我 们假设已经找到一种把N－1个金盘从一根柱搬到另外一根柱的方 法，那么，我们只要把N－1个金盘从A搬到C，然后把最大的金 盘从A搬到B，最后把C上的N一1个金盘搬到B就可以了。靠递归 的思想，我们轻而易举地完成了整个搬动。
递归，顾名思义，其包含了两个意 思：递 和 归
小试牛刀：案例1
有5个人坐在一起， 问第5个人多少岁，他 说比第4个人大2岁；问第4个人多少岁，他 说比第3个人大2岁；问第3个人多少岁，他 说比第2个人大2岁；问第2个人多少岁，他 说比第1个人大2岁；最后问第一个人多少 岁，他说是10岁，请问第5个人多少岁？
(3)编写程序
Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String,
ByVal C As String, t As Long)
(2)设计算法。
我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘 需要从A柱搬到B柱(以C柱为过渡)。那么完成它只需3步：
①Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1个金 盘搬到C柱；
② A→B 它的意思是把一个(最大的)金盘从A柱搬到B柱； ③ Hanoi(N－1，C，B，A)它的意思是把c柱上的N一1个金 盘搬到B柱。
第一，一次只能移动一个金盘。
第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。
第三，任何时候都不能把大的金盘放在小的金盘上。
神话说，如果僧人把64个金盘完全地从一根宝石移到了另外 一根上，世界的末日就要到了。当然，神话只能当故事来听， 世界不可以因为个别人的活动而导致末日。不过，从僧人搬完 64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金 盘，那也得要几千亿年！
子问题，这些子问题可以用相同的解题思路来解决，当问题足够 小，直接给出解答，然后层层返回，随着子问题的逐步解决，最 终大问题随之得到答案。 在函数实现时，因为解决大问题的方法和解决小问题的方法是同 一个方法，所以就产生了函数调用它自身的情况
辩一辩：
从前有座山，山里有个庙，庙里有 个老和尚他在讲故事，讲的什么故 事呢？“从前有座山，山里有个庙， 庙里有个老和尚他在讲故事……”
1: b = 1 • ③i = 3 • ④c = a + b：a = b：b = c • ⑤i=i+1,如果i≤N则返回④ • ⑥结束
递归解法：
假设第N个月的兔子数目是F(N)， 我们有：
(3)编写程序 非递归程序：
递归程序：
• Private Sub Command1_Click()
Function Fib(ByVal N As Integer) As Long
(1)分析问题，构建数学模型
1月 2月
小兔 1
大兔
1
合计 1 1
3月 4月 5月 6月 7月 8月 9月 10月 11月 12月
1
1
2
3
5
8
13 21 34 55
1
2
3
5
8
13 21 34 55 89
2
3
5
8
13 21 34 55 89 144
Hale Waihona Puke (2)设计算法。 非递归解法：
• ①输入计算兔子的月份数：N • ②If N < 3 Then c = 1 Else a =
辩一辩：
你用钥匙打开面前这扇门，看到屋里 面还有一扇门。你走过去，发现手中 的钥匙还可以打开它，你推开门，发 现里面还有一扇门，你继续打开它……
学以致用：案例2：
著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》 中提出了一个“兔子问题”：假定小兔子一个月就可以长成大 兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一 对小兔子，问到年底时将有多少对兔子? (当然得假设兔子没有 死亡而且严格按照上述规律长大与繁殖)
高二 信息技术 《算法与程序设计》选修
4.5 递归算法与递归程序
“像中像”现象
甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反 反复复，就会产生一连串的“像中像”。这是一种类递归现象。
4.5 递归算法与递归程序
轻松一刻：
“报数游戏”
1：递归定义：
递归算法：是指在函数（或过程）定 义中又调用函数（或过程）自身的方 法。即自己调用自己。
• End Sub
3：递归算法的特点：
(1)递归就是在自定义函数或过程中调用自身。 (2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3)递归算法解题通常简洁易懂。 (4)递归算法的实质是把问题转化为规模缩小了的同类问题
拓展提升：案例3：
传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝 石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小 不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根 上。僧人在移动金盘时遵守下面3条规则：
Private Sub Command1_Click()
• a=b
N = Val(Text1.Text)
• b=c
Text2.Text = "第" & N & "月的兔子数目是： " & Fib(N)
• Next i
End Sub
• Text2.Text = "第" & N & "月的兔子数
目是：" & c
• N = Val(Text1.Text)
If N < 3 Then Fib = 1 Else Fib = Fib(N - 1)
• If N < 3 Then c = 1 Else a = 1: b = 1 + Fib(N - 2)
• For i = 3 To N
End Function
• c=a+b