数据结构与算法课程报告

数据结构与算法课程报告递归算法的原理与应用举例学号姓名班级2011级电子2班华侨大学电子工程系1、递归算法的介绍与简要分析递归是解决一类问题的重要方法。递归算法是算法设计中常用的一种方法， 它可以解决具有递归属性的问题，并且是行之有效的。递归算法结构清晰，而且 容易用数学归纳法来证明算法的正确性等优点，因此它为设计算法、调试程序 带 来很大方便。我们先举一个简单的例子来说明。我们知道，在数学中N!般定义为:N =1*2*3*(N-1)*N但也可以用下面公 式来定义：若 N=0 N!=1；若 N0 N!= N*(N-1)! 在N0的公式中，又包括了(N-1)!,这就是N!的递归定义。一般说，如果一个对象部分的有自己组成，或者是按他自己定义的，则称之 为是递归的。 递归在数学和计算机学科中经常遇到。利用递归方法可以用有限 的语句来定义无限集合，但在递归定义中至少要有一条是非递归的，即初始定义。 否则就会产生逻辑性错误。在计算机科学中，递归概念还经常用于递归调用方面，即函数或过程自己调 用自己。用递归调用的算法就是递归算法。 递归调用会产生无终止运算的可能 性，因此必须在适当的情况下终止递归调用(也叫做边界条件)。根据递归定义设 计的递归算法中，非递归的初始定义就用做程序的终止条件。递归算法就是算法中有直接或间接调用算法本身的算法。递归算法的要点 是：(1) 递归就是在过程或函数里调用自身。 (2)问题具有类同自身的子问题的性 质，被定义项在定义中的应用具有更小的尺度。 (3)被定义项在最小尺度上有直 接解。 (4)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出 口。归算法设计的原则是用自身的简单情况来定义自身，一步比一步更简单，确 定递归的控制条件非常重要。设计递归算法的方法是： (1)寻找方法，将问题化为原问题的子问题的求解。 (2)设计递归出口，确定递归 终止条件。2. 递归算法的特点递归就是在过程或函数里调用自身 。 递归程序在执行过程中总是不断地调 用自身， 而每次调用自身时， 通常在规模上都有所缩小， 当问题的规模缩小 到某一值时就可以直接给出解答而不再进行递归调用，因而每次递归调用都是有 条件的(以规模未达到直接解答的大小为条件)， 而且相邻两次调用之间有紧 密的联系， 前一次要为后一次做准备 (通常前一次的输出就作为后一次的输 入)，在使用递归策略时，必须有一个明确的递归结束条件，也称为递归出口 。递归算法一般用于解决三类问题：(1) 数据的定义是按递归定义的， 如 Fibonacci 函数 。(2) 问题解法按递归算法实现， 如回溯问题 。(3) 数据的结构形式是按递归定义的， 如树的遍历， 图的搜索等 。递归算法设计的基本思想是： 对于一个复杂的问题， 把原问题分解为若干 个相对简单的同类子问题， 继续下去直到子问题简单到能够直接求解， 也就是 说到了递归的出口， 这样原问题就有递推得解 。 所以在使用递归算法时， 首 先要弄清楚简单情况下的解法， 然后弄清楚如何把复杂情况归纳为更简单的情 况。3. 递归算法的分类递归算法一般通过函数或子过程来实现 。 在函数或子过程的内部，直接或者间 接地调用自己的算法 。 所以根据递归算法的表示形式， 可以将递归算法分为 递归函数和递归子过程两种； 根据递归算法调用的形式可以有直接递归和间接 递归两种 。 如图所示是直接递归和间接递归调用过程的示意图 。二、 递归算法的应用（一） 汉诺塔问题有三根针A、B、c。A针上有，1个盘子，大的在下，小的在上，要求把这，1 个盘子从A针移到c针，在移动的过程中可以借助B针，每次只允许移动一个 盘子，且在移动过程中在三根针上都保持 大盘在下，小盘在上。关于这个递归问题的实例，教材与一般文献中都是直接介绍移动11，个盘子的 算法。对学生来说，一个 不确定的数n概念上太抽象，对算法的理解、依据 算法编程带来很大难度。在教学过程中，笔者先从一个 确定的数字（n=3）来分析 移动过程，模拟程序的执行过程。假设A针上有3个（编号为I、II、III）的盘子移到C针上，现来看一下解决 问题的步骤：将A针上2个（编号为1、11）盘子移到B针上（借助c针）：1）将A针上I号盘子移到c针上2）将A针上II号盘子移到B针上3）将C针 上I号盘子移到B针上（2）将A针上III号盘子移到c针上。将B针上2个（编号为I、II ）盘子移到c针上（借助A针）：1）将B针上I号盘子移到A针上2）将B针上II号盘子移到C针上3）将A 针上 I 号盘子移到 C 针上上述3个步骤中， （1）、 （3）两步的解法与原来移动3个盘子的解法完全相同，只 是盘子数目减少为 2，并且代表源针、工作针、目标针的针代号不同而已；问题 可以用递归方法解决，结束递归的条件就是 ，l= 1 时，只需要简单地把一个盘 子从源针移到目标针上即可。事实上，上面3 个步骤包含两种操作：(1)将 2 个 盘子从一个针移到另一个针上，依据题意，每次移动过程都是一个对不同数目的 盘子进行相似的动作， 这是一个递归的过程，用 hanoi 函数实现。(2)将每次移 动的最后 1个盘子从一个针上移到另一针上，用 move 函数实现。通过上述3 个盘子的移动过程的分析，学生基本能了解盘子移动过程中算法的具 体实现，接着依据上述模式，来分析移动n个盘子的过程。这时，只要将上述程 序过程中的数字作相应的改变即可。将凡个盘子从A针移到C针可以也分解为上述3个步骤，同样，从上述3个步骤 分析可知，其中也包含两种操作：(1)将多个盘子从一个针移到另一个针上，这 是一个递归的过程，用hanoi函数实现(见程序1)。(2)将1个盘子从一个针上 移到另一针上，用move函数实现(见程序2)。程序 1 ：void han (int n， char one， char two， char three)/将 n 个盘子从 one 借助 two 移到 three 针上(注意各参数的含义) if(n=1) move (one， three) ；/递归出口 else han (n 一 1， one， three， two) ； move(one， three) ；han (n 一 1， two， one， three) ； 程序 2：void move (char getone， char putone) coutgetone”_+putoneendl；就n个盘子的移动过程，算法的设计与程序的编写，都与移动3个盘子很相似， 理解起来就容易多了。(二)树的遍历 递归的一个典型的应用就是树的遍历。目录系统也是树形的结构，有时我们也可 能会对目录树进行遍历，比如进行文件的搜索。以下是一个对目录进行递归处理 的程序，它先处理最上一层目录的中的内容，取得其中的一个元素，判断它是文 件还是目录，如果是文件，则列印出它的绝对目录名，如果是一个目录，则进行 递归。这个程序中使递归终止的条件是，处理的元素不是目录。递归函数的参数 值总是在文件和目录之间变化。二叉树是数据结构中最常见的存储形式，树与森林都可以转换为二叉树，而遍历 算法则是二叉树最重要的操作。在遍历算法中，递归算法是最普遍的，弄清了递 归算法及执行时栈的变化情况，可设计出较好的非递归化算法。下面讨论二叉树 中序遍历递归算化栈的变化情况。二叉树的中序递归遍历算法如下： 若二叉树为空，则返回，否则1) 中序遍历左子树 (L)2) 访问根结点 (v)3) 中序遍历右子树 (R)下面以图一为例分析其执行过程中栈的变化情况。递归调用中，每次入栈的内容， 包括参数(即结点信息)与返回地址，由于返回地址已在流程中反映出来，故在栈 中不再列出：分析可看出，每个元素入栈与出栈两次。在第一次出栈时访问它，输出结果为： 4，3，5，2，1，7，6，8，9。面是将我们一些常见的经典算法用递归算法用 VB 来实现 。【 例 1 】 用递归算法求自然数 n 的阶乘 。分析： 要求 n 的阶乘， 只要求出 n-1 的阶乘， 则 n!=n*(n-1)!， 可以定 义一个函数fact(n),表示求n!,则递归表达式为：fact(n)二n*fact(n-l), 递归的终止条件是当 n=1 或者 n=0 时, fact(n)=1 。 递归函数如下：PrivateFunctionfact(ByValnAsInteger)AsLong 求 n 的阶乘Ifn=1Orn= 0Thenfact=1Elsefact= n*fact(n-1)EndIf EndFunction【例2】用递归算法求斐波那契(Fibonacci)数列第n项的值。分析： 根据 Fibonacci 数列的特点, 可以定义一个函数 fib(n) , 表示求 Fibonacci 数列第 n 项的值, 则递归表达式为： fib(n)=fib(n-1)+fib(n-2) , 递归的终止条件是当 n=1 或者 n=2 时, fib(n)=1 。 递归函数如下：PrivateFunctionfib(ByValnAsInteger)AsInteger求Fibonacci数列第n项的值Ifn=1Orn=2Thenfib=1Elsefib= fib(n-1)+ fib(n-2)EndIfEndFunction【例3】用递归算法求1n个连续自然数的和。分析： 可以定义一个函数 sum(n)， 表示求 1n 个连续自然数的和，则递归 表达式为：sum(n)二n+sum(n-1),递归的终止条件是当n=1时，sum (n)=1。 递归函数如下：PrivateFunctionsum(ByValnAsInteger)AsInteger 求 1 n 个连续自然数的和Ifn=1Thensum =1Elsesum = n+sum(n-1)EndIfEndFunction【 例 4 】 用递归算法实现字符串的反序 。分析：要对一个由 n 个字符组成的字符串反序，只要对该字符串前面的 n-1 个字符实现反序， 就可以很容易实现该字符串的反序 。 可以定义一个函数 reverse(st),表示对字符串st实现反序，则递归表达式为：re-verse(st)二 Right(st,1)&reverse(Left(st,Len(st)-1)， 递归的终止条件是当 Len(st) 1时，reverse(st)二st。递归函数如下：PrivateFunctionreverse(stAsString)AsString 字符串反序IfLen(st)=1Thenreverse=stElsereverse= Right(st,1)& reverse(Left(st,Len(st)-1)EndIfEndFunction【 例 5 】 用递归算法实现将一个十进制整数转换成二进制 。分析： 可以定义一个递归函数 trans(n)， 表示将一个十进制整数 n 转换成二 进制，不难得出它的递归表达式为：trans(n)二trans(n2)& (n M od2),当n=l 或者 n=0 时， trans(n)= n， 递归函数如下：PrivateFunctiontrans(ByValnAsInteger)AsStringIfnmax(a()，n-1)， 则 max=a(n) ， 否则 max=max(a()，n-1) ， 递归函数如下：PrivateFunction M ax(a()AsInteger，ByValnAsInteger)AsIntegerIfn=1ThenM ax= a(1)ElseM ax= M ax(a,n-1)Ifa(n) M axThen M ax= a(n)EndIfEndFunction【 例 8 】 用递归算法实现数组的从大到小排序 。分析： 要对数组 a 中所有元素进行排序， 若能对前 n-1 个元素进行 排序(假 设数组 a 中共有 n 个元素)， 则在排序好的 n-1 个元素中找到插入位置， 再 将 a ( n ) 插入到该位置即可， 同样的要对数组 a 中 n-1 个元素进行排序， 则先排序好 n-2 个元素， 如此下去， 当 n=1 时， 递归结束 。可以定义一 个递归子过程 sort(a(),n)， 功能是实现数组 a 中前 n 个元素排序 。 递归 子过程如下：PrivateSubsort(a()AsInteger,nAsInteger)Dim iAsInteger,posAsIntegerDim tempAsIntegerIfn1ThenCallsort(a,n-1)Fori=1Ton-1 找插入位置Ifa(n)= a(i)ThenExitForEndIfNexti pos=i temp= a(n)Fori= n-1ToposStep-1 循环移位a(i+1)= a(i)Nexti a(pos)=tempEndIfEndSub三、算法的坏例子递归算法设计的难点是递归函数的参数设置和返回值(地址)的设定。如这两 个问题没解决好则容易出错。尽管递归算法有如此的优点，但递归算法还是有缺点的，如递归算法的时间 效率低，因此有的问题虽然可以用递归法求解，但为了算法的时间效率，还是用 非递归法求解为好。另外，（在递归调用的过程当中系统为每一层的返回点、局 部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。递归次数过多容易造成栈溢出等 。 所以一般不提倡用递归算法设计程序 。 例如以上介绍的求斐波那契（Fibonacci）数列第n项值的递归过程，调用一 次要产生两个新的调用， 递归次数呈指数增长， 时间复杂度为 O（2n）， 若 用非递归法求解， 它的时间复杂度为 O（n） 。