递归vb.ppt

递归 递归现象 两面镜子中间的你，产生“像中像”，就是这是一种递归现象。 是一种直接或者间接地调用自身的算法。 直接递归：在函数f中直接调用函数f f f 简接递归：在函数f中调用其他函数 而其他函数又调用函数f f g f 递归函数 递归算法的实质 是把问题转化为规模缩小了的同类问题的子问题；然后递归调用函数(或过程)来表示问题的解。 递归算法所体现的“重复”一般有三个要求： 1.每次调用在规模上都有所缩小； 2.相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 3.在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。 思考： 1.在上述fac函数中，若少了： If n = 1 Then fac = 1 即只有语句： fac = n * fac(n-1) 程序运行结果将如何？ 2.若调用时n=-4，则程序运行结果？ 一、定义是递归的 例：斐波那契(Fibonacci)数列 著名的意大利数学家在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?? 编写程序 Sub Hanoi(n%, A$, B$ ,C$, ByRef t) If n = 1 Then ListBox1.Items.Add(A + → + C) Else Call Hanoi(n - 1, A, C, B, t) ‘ A移到B借助于C ListBox1.Items.Add(A + → + B) Call Hanoi(n - 1, B, A ,C, t) ‘ B移到C借助于A End If t = t + 1 增加变量t用来统计移动次数。 End Sub 递归函数 数组逆转 递归程序使得a数组所有元素的逆转，例： 原始数据： 56 21 34 9 12 33 2 98 1 83 逆转后数据：83 1 98 2 33 12 9 34 21 56 本课程掌握三种图形： 1.三角形 2.四边形 3.树 递归三角形 从1个大的三角形开始，将其三条边的中点进行连线，分成相同的4个三角形，除中间外的3个三角形重复上述过程，直到满足给定的条件底层为止。 Sub Sier3(x1!, y1!, x2!, y2!, x3!, y3!, n%) Dim u1!, v1!, u2!, v2!, u3!, v3! If n = 1 Then g.DrawLine(p, x1, y1, x2, y2) g.DrawLine(p, x2, y2, x3, y3) g.DrawLine(p, x3, y3, x1, y1) Else u1 = (x1 + x2) / 2 v1 = (y1 + y2) / 2 u2 = (x2 + x3) / 2 v2 = (y2 + y3) / 2 u3 = (x3 + x1) / 2 v3 = (y3 + y1) / 2 Sier3(x1, y1, u1, v1, u3, v3, n - 1) Sier3(u1, v1, x2, y2, u2, v2, n - 1) Sier3(u3, v3, u2, v2, x3, y3, n - 1) End If End Sub 递归四边形 u1 = x1 * 2 / 3 + x2 / 3 v1 = y1 * 2 / 3 + y2 / 3 u2 = x1 / 3 + x2 * 2 / 3 v2 = y1