5.5 递归算法实例及程序实现 课件（15张幻灯片）

课件15张PPT。递归算法实例及程序实现递归递归现象
两面镜子中间的你，产生“像中像”，就说这是一种递归现象。
递归是程序设计中经常使用的方法，这是因为用递归的方法，能
简洁地描述某些看来复杂的问题的算法。递归算法递归算法的基本思想是：
把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小、小事化了”。而计算过程中递归的展开与递归的返回则是由计算机自动地进行。递归算法的概念
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。直接递归：在函 f f
间接递归：在函 f g f
例1 小猴吃桃问题。有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一个，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?建立数学模型：
假设第n（n<10）天的桃子数为tao(n)那么，
tao=10 n=1
tao(n)=(tao(n+1)+1)*2 n<10算法描述：
fun_ction 你有多少桃子？（第几天）
如果我第10天，那么我就只有一个桃子。
否则，我的桃子数=（后一天的桃子数+1）*2
end fun_ction编程实现：
Private Sub Command1_Click()
Dim n,t As Integer
n= 1
t=tao (n) ‘调用函数
Print t
End Sub
Function tao(n As Integer) As Integer ‘ 递归函数
If n = 10 Then
tao = 1 ‘ 终止条件
Else
tao = (tao(n + 1) + 1) * 2
End If
End Function递归算法的实现要点：
递归调用必须是有限制的，有限才有意义。所以在进行算法描述
时必须设置相关的控制条件，使其成为有限。这可以通过条件语
句（If语句）来实现，即只有在设定的条件成立时递归才继续，否
则终止递归。可见，构成递归的必须满足以下条件：（1）有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值；（2）函数的描述中包含其本身，即能用递归形式表示，且递归
终止条件的发展。递归算法例2 阶乘函数。例如，对于问题fact(4),递归的展开是：递归的返回是问题fact(4)的计算结果为24。VB允许一个自定义函数在函数体的内部调用自己，这样的函数就叫递归函数。　主函数用实参n = 4调用了递归算法fact(4)，而fact(4)要通过调用fact(3)、fact(3)要通过调用fact(2)、fact(2)要通过调用fact(1)来得出计算结果。fact(4)的递归调用过程如下图所示，其中，实线箭头表示函数调用，虚线箭头表示函数返回，此函数在返回时函数名将带回返回值。例2 阶乘函数 （求 4！）递归函数 ■ 为什么能计算n!
考察程序执行过程:Function fact(n )
If(n=1)
fact=1
Else
fact=n*fact(n-1)
End If
End Function Function fact(n)
If(n=1)
fact=1
Else
fact=n*fact(n-1)
End If
End Function Function fact(n)
If(n=1)
fact=1
Else
fact=n*fact(n-1)
End If
End Function Function fact(n)
If(n=1)
fact=1
Else
fact=n*fact(n-1)
End If
End Function 第一次调用开始：n为4递归算法
Function fact(n As Integer) As Long
If n<=1 Then
fact=1
Else
fact=n*fact(n-1)
End If
End Function Private Sub Command1_Click()
Dim nk As Long
Dim n As Integer
n = Val(Text1.Text)
nk=fact(n)
Text2.Text = str(nk)
End Subn=3n=2n=1返回fact=24 返回fact=6 返回fact=2 返回fact=1递推回归递归算法的总结如下：递归方法它利用自己定义自己的方式来表述或定义函数、过程和语言构造或作为求解问题的方法。
递归算法是一种允许在函数或过程的执行过程中，直接或间接调用自身的算法，为解决某一问题，算法采用多次调用自身，把要解决的问题转变成类型相同，但规模越来越小的问题的方式来求得原问题的最终解。例3 汉诺塔问题。（教材P120）
汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：
（1）一次只能移动一个盘子；
（2）移动过程中大盘子不能放在小盘子上面；
（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。　　问题分析：可以用递归方法求解n个盘子的汉诺塔问题。4个盘子汉诺塔问题的递归求解示意图如图所示基本思想
1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递
归表示为:
(1)把上边的n-1个盘子看成一组从A柱移到B柱;[h(n-1)次搬动]
(2)把最下边的一个盘子从A柱移到C柱; [1次搬动]
(3)把移到B柱的n-1个盘子再移到C柱。[h(n-1)次搬动] 这样，把n个盘子从A搬到C所需的搬动次数h(n)=h(n-1)+1+h(n-1)=2*h(n-1)+1递归算法把移动n个盘子的汉诺塔问题分解为移动n-1个盘子的汉诺塔问题，把移动n-1个盘子的汉诺塔问题分解为移动n-2个盘子的汉诺塔问题，…，把移动2个盘子的汉诺塔问题分解为移动1个盘子的汉诺塔问题。对于1个盘子的汉诺塔问题直接求解。在1个盘子的汉诺塔问题解决后，可以解决2个盘子的汉诺塔问题，…,在n-1个盘子的汉诺塔问题解决后，可以解决n个盘子的汉诺塔问题。这样，n个盘子的汉诺塔问题最终就得以解。
递归算法的执行过程可总结如下：
递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序逐层返回；返回到最外层的调用语句时递归算法执行过程结束。可见，递归的实现过程包含了“调用”和“返回” 两个阶段。1．求1+2+3+4+5……N （用递归算法编程实现）。
2．用递归算法实现“猴子吃桃”问题求解。上机任务：