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递推回归递归算法的总结如下：递归方法它利用自己定义自己的方式来表述或定义函数、过程和语言构造或作为求解问题的方法。 递归算法是一种允许在函数或过程的执行过程中，直接或间接调用自身的算法，为解决某一问题，算法采用多次调 ... ...