高中信息技术-45递归算法与递归程序教学教学课件

4.5递归算法与递归程序高二信息技术《算法与程序设计》选修4.5递归算法与递归程序高二信息技术《算法与程序设计“像中像”现象甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种类递归现象。“像中像”现象甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，4.5递归算法与递归程序4.5递归算法与递归程序“报数游戏”轻松一刻：“报数游戏”轻松一刻：

递归算法：是指在函数（或过程）定义中又调用函数（或过程）自身的方法。即自己调用自己。1：递归定义：递归，顾名思义，其包含了两个意思：递和归递归算法：是指在函数（或过程）定义中又调用函数（或过程）小试牛刀：案例1

有5个人坐在一起，问第5个人多少岁，他说比第4个人大2岁；问第4个人多少岁，他说比第3个人大2岁；问第3个人多少岁，他说比第2个人大2岁；问第2个人多少岁，他说比第1个人大2岁；最后问第一个人多少岁，他说是10岁，请问第5个人多少岁？

分析思考：尝试用递归思想设计数学模型小试牛刀：案例1

有5个人坐在一起，问第5个人多少岁，他案例1递归函数：Functions(byvalnasinteger)

AsIntegerIf

n=1

then

s=10

else

s=s(n-1)+2endifEndfunction案例1递归函数：Functions(byvalnas2：递归思想的内涵：有去有回才是递归。递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，当问题足够小，直接给出解答，然后层层返回，随着子问题的逐步解决，最终大问题随之得到答案。在函数实现时，因为解决大问题的方法和解决小问题的方法是同一个方法，所以就产生了函数调用它自身的情况2：递归思想的内涵：有去有回才是递归。辩一辩：从前有座山，山里有个庙，庙里有个老和尚他在讲故事，讲的什么故事呢？“从前有座山，山里有个庙，庙里有个老和尚他在讲故事……”辩一辩：从前有座山，山里有个庙，庙里有个老和尚他在讲故事，讲你用钥匙打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它……辩一辩：你用钥匙打开面前这扇门，看到屋里面还有一扇门。你走过去，发现学以致用：案例2：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?

(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)学以致用：案例2：著名的意大利数学家斐波那契(Fibon(1)分析问题，构建数学模型(1)分析问题，构建数学模型假设第N个月的兔子数目是F(N)，我们有：(2)设计算法。①输入计算兔子的月份数：N②IfN<3Thenc=1Elsea=1:b=1③i=3④c=a+b：a=b：b=c⑤i=i+1,如果i≤N则返回④⑥结束非递归解法：递归解法：假设第N个月的兔子数目是F(N)，我们有：(2)设计算法。①PrivateSubCommand1_Click()

N=Val(Text1.Text)

IfN<3Thenc=1Elsea=1:b=1

Fori=3ToN

c=a+b

a=b

b=c

Nexti

Text2.Text="第"&N&"月的兔子数目是："&cEndSub

FunctionFib(ByValNAsInteger)AsLong

IfN<3ThenFib=1ElseFib=Fib(N-1)+Fib(N

-2)EndFunctionPrivateSubCommand1_Click()

N=Val(Text1.Text)

Text2.Text="第"&N&"月的兔子数目是："&Fib(N)EndSub(3)编写程序非递归程序：递归程序：PrivateSubCommand1_Click()

F3：递归算法的特点：(1)递归就是在自定义函数或过程中调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常简洁易懂。(4)递归算法的实质是把问题转化为规模缩小了的同类问题3：递归算法的特点：(1)递归就是在自定义函数或过程中调用自拓展提升：案例3：

传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：

第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个别人的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！拓展提升：案例3：传说在古代印度的贝拿勒斯神庙，有一块黄(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)分析问题我们把3根宝石柱分别命名为A、B、C。最初有N

我们定义一个过程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柱。(2)设计算法。我们定义一个过程Hanoi(N，A，B，(3)编写程序PrivateSubHanoi(nAsInteger,ByValAAsString,ByValBAsString,ByValCAsString,tAsLong)Ifn=1ThenText3.Text=Text3.Text+A+"→"+B+vbCrLft=t+1

'增加变量t用来统计移动次数。Else

CallHanoi(n-1,A,C,B,t)

Text3.Text=Text3.Text+A+"→"+B+vbCrLf

t=t+1

CallHanoi(n-1,C,B,A,t)EndIfEndSubPrivateSubCommand1_Click()

DimtAsLong,nAsInteger

t=0

n=Val(Text1.Text)

A="A"

B="B"

C="C"

CallHanoi(n,A,B,C,t)

Text2.Text=tEndSub(3)编写程序PrivateSubHanoi(nAs4：递归算法的效率分析：探究1）：分析报数游戏中两种报数方法的效率？探究2）：程序运行效率分析？

兔子问题非递归程序

兔子问题递归程序

汉诺塔问题递归程序4：递归算法的效率分析：探究1）：分析报数游戏中两种报数方法4：递归算法的效率分析：1)递归算法解题通常简洁易懂，极具美感，但在程序运行过程中存在着大量重复的函数调用，耗费了计算机时间和资源，所以递归算法解题的运行效率较低。2)在递归调用的过程中系统会为每一层的返回点、局部量等开辟栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序，尤其是规模较大的问题。4：递归算法的效率分析：1)递归算法解题通常简洁易懂，极具美5：递归法解题小结：1）、明确递归终止条件；2）、给出递归终止时的处理办法；3）、找出递推关系式，不断缩小问题规模。递归法编程模型：functionf(大规模)if结束条件then给出答案else通过含f(小规模)的递推式，缩小规模

endifendfunction

5：递归法解题小结：1）、明确递归终止条件；递归法编程模型：课堂练习：1、求n!问题Functionf(ByValnAsInteger)Ifn=0orn=1Thenf=1Elsef=EndIfEndFunctionn*f(n-1)2、猴子吃桃：每次吃掉一半多一个，直到第10天只剩一个，第一天共摘了多少个桃子？Functiongtao(ByValdayAsInteger)Ifday=10thentao=1Elsetao=EndifEndfunction（Tao(day+1)+1)*2课堂练习：1、求n!问题n*f(n-1)2、猴子吃桃1：递归定义：课堂总结：2：递归思想的内涵：3：递归算法的特点：4：递归算法的效率分析：5：递归法解题小结：1：递归定义：课堂总结：2：递归思想的内涵：3：递归算法的特谢谢大家！谢谢大家！4.5递归算法与递归程序高二信息技术《算法与程序设计》选修4.5递归算法与递归程序高二信息技术《算法与程序设计“像中像”现象甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，而且这样反反复复，就会产生一连串的“像中像”。这是一种类递归现象。“像中像”现象甲镜子里有乙镜子的像，乙镜子里也有甲镜子的像，4.5递归算法与递归程序4.5递归算法与递归程序“报数游戏”轻松一刻：“报数游戏”轻松一刻：

递归算法：是指在函数（或过程）定义中又调用函数（或过程）自身的方法。即自己调用自己。1：递归定义：递归，顾名思义，其包含了两个意思：递和归递归算法：是指在函数（或过程）定义中又调用函数（或过程）小试牛刀：案例1

有5个人坐在一起，问第5个人多少岁，他说比第4个人大2岁；问第4个人多少岁，他说比第3个人大2岁；问第3个人多少岁，他说比第2个人大2岁；问第2个人多少岁，他说比第1个人大2岁；最后问第一个人多少岁，他说是10岁，请问第5个人多少岁？

分析思考：尝试用递归思想设计数学模型小试牛刀：案例1

有5个人坐在一起，问第5个人多少岁，他案例1递归函数：Functions(byvalnasinteger)

AsIntegerIf

n=1

then

s=10

else

s=s(n-1)+2endifEndfunction案例1递归函数：Functions(byvalnas2：递归思想的内涵：有去有回才是递归。递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，当问题足够小，直接给出解答，然后层层返回，随着子问题的逐步解决，最终大问题随之得到答案。在函数实现时，因为解决大问题的方法和解决小问题的方法是同一个方法，所以就产生了函数调用它自身的情况2：递归思想的内涵：有去有回才是递归。辩一辩：从前有座山，山里有个庙，庙里有个老和尚他在讲故事，讲的什么故事呢？“从前有座山，山里有个庙，庙里有个老和尚他在讲故事……”辩一辩：从前有座山，山里有个庙，庙里有个老和尚他在讲故事，讲你用钥匙打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它……辩一辩：你用钥匙打开面前这扇门，看到屋里面还有一扇门。你走过去，发现学以致用：案例2：著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?

(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)学以致用：案例2：著名的意大利数学家斐波那契(Fibon(1)分析问题，构建数学模型(1)分析问题，构建数学模型假设第N个月的兔子数目是F(N)，我们有：(2)设计算法。①输入计算兔子的月份数：N②IfN<3Thenc=1Elsea=1:b=1③i=3④c=a+b：a=b：b=c⑤i=i+1,如果i≤N则返回④⑥结束非递归解法：递归解法：假设第N个月的兔子数目是F(N)，我们有：(2)设计算法。①PrivateSubCommand1_Click()

N=Val(Text1.Text)

IfN<3Thenc=1Elsea=1:b=1

Fori=3ToN

c=a+b

a=b

b=c

Nexti

Text2.Text="第"&N&"月的兔子数目是："&cEndSub

FunctionFib(ByValNAsInteger)AsLong

IfN<3ThenFib=1ElseFib=Fib(N-1)+Fib(N

-2)EndFunctionPrivateSubCommand1_Click()

N=Val(Text1.Text)

Text2.Text="第"&N&"月的兔子数目是："&Fib(N)EndSub(3)编写程序非递归程序：递归程序：PrivateSubCommand1_Click()

F3：递归算法的特点：(1)递归就是在自定义函数或过程中调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常简洁易懂。(4)递归算法的实质是把问题转化为规模缩小了的同类问题3：递归算法的特点：(1)递归就是在自定义函数或过程中调用自拓展提升：案例3：

传说在古代印度的贝拿勒斯神庙，有一块黄铜板上插了3根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规则：

第一，一次只能移动一个金盘。第二，每个金盘只能由一根宝石柱移到另外一根宝石柱。第三，任何时候都不能把大的金盘放在小的金盘上。神话说，如果僧人把64个金盘完全地从一根宝石移到了另外一根上，世界的末日就要到了。当然，神话只能当故事来听，世界不可以因为个别人的活动而导致末日。不过，从僧人搬完64个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，那也得要几千亿年！拓展提升：案例3：传说在古代印度的贝拿勒斯神庙，有一块黄(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)分析问题我们把3根宝石柱分别命名为A、B、C。最初有N

我们定义一个过程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柱。(2)设计算法。我们定义一个过程Hanoi(N，A，B，(3)编写程序PrivateSubHanoi(nAsInteger,ByValAAsString,ByValBAsString,ByValCAsString,tAsLong)Ifn=1ThenText3.Text=Text3.Text+A+"→"+B+vbCrLft=t+1

'增加变量t用来统计移动次数。Else

CallHanoi(n-1,A,C,B,t)

Text3.Text=Text3.Text+A+"→"+B+vbCrLf

t=t+1

CallHanoi(n-1,C,B,A,t)EndIfEndSubPrivateSubCommand1_Click()

DimtAsLong,nAsInteger

t=0

n=Val(Text1.Text)

A="A"

B="B"

C="C"

CallHanoi(n,A,B,C,t)

Text2.Text=tEndSub(3)编写程序PrivateSubHanoi(nAs4：递归算法的效率分析：探究1）：分析报数游戏中两种报数方法的效率？探究2）：程序运行效率分析？

兔子问题非递归程序

兔子问题递归程序