数据结构与算法课程报告-递归算法的原理与应用举例

发布时间：2024-11-10

数据结构与算法课程报告

递归算法的原理与应用举例

学号

姓名

班级 2011级电子2班

华侨大学电子工程系

一、递归算法原理与介绍

1、递归算法的介绍与简要分析

递归是解决一类问题的重要方法。递归算法是算法设计中常用的一种方法，它可以解决具有递归属性的问题，并且是行之有效的。递归算法结构清晰，而且容易用数学归纳法来证明算法的正确性等优点，因此它为设计算法、调试程序带来很大方便。我们先举一个简单的例子来说明。

我们知道，在数学中N!一般定义为:N=1*2*3*…*(N-1)*N 但也可以用下面公式来定义：{若N=0 N！＝1；若N>0 N!= N*(N-1)！}

在N>0的公式中，又包括了(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、Ⅱ、Ⅲ)的盘子移到 C针上，现来看一下解决问题的步骤：

(1)将A针上2个(编号为 I、Ⅱ)盘子移到B针上(借助 c针)：

1)将A针上 I号盘子移到c针上 2)将 A针上Ⅱ号盘子移到 B针上 3)将 C针上 I号盘子移到 B针上 (2)将A针上Ⅲ号盘子移到c针上。

(3)将B针上2个(编号为I、Ⅱ)盘子移到 c针上(借助A针)：

1)将 B针上 I号盘子移到 A针上 2)将 B针上 Ⅱ号盘子移到 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) {cout<<getone<<”

_+"<<putone<<endl；}

就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-1)，递归

的终止条件是当 n=1 或者 n=0 时，fact(n)=1 。递归函数如下：

PrivateFunctionfact(ByValnAsInteger)AsLong

' 求 n 的阶乘

Ifn=1Orn= 0Then

fact=1

Else

fact= 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=2Then

fib=1

Else

fib= fib(n-1)+ fib(n-2)

EndIf

EndFunction

【例 3 】用递归算法求 1 ～ n 个连续自然数的和。

分析：可以定义一个函数 sum(n)，表示求 1~n 个连续自然数的和，则递归表达式为：sum(n)=n+sum(n-1)，递归的终止条件是当 n=1 时，sum (n)=1 。递归函数如下：

PrivateFunctionsum(ByValnAsInteger)AsInteger

' 求 1 ～ n 个连续自然数的和

Ifn=1Then

sum =1

Else

sum = n+sum(n-1)

EndIf

EndFunction

【例 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)<=1Then

reverse=st

Else

reverse= Right(st,1)& reverse(Left(st,Len(st)-1))

EndIf

EndFunction

【例 5 】用递归算法实现将一个十进制整数转换成二进制。

分析：可以定义一个递归函数 trans(n)，表示将一个十进制整数 n 转换成二进制,不难得出它的递归表达式为：trans(n)=trans(n\2)& (n M od2)，当 n=1 或者 n=0 时，trans(n)= n，递归函数如下：

PrivateFunctiontrans(ByValnAsInteger)AsString

Ifn<=1Then

trans= n

Else

trans=trans(n\2)& (n M od2)

EndIf

EndFunction

【例 6 】用递归算法实现求数组元素之和。

分析：可以定义一个递归函数 sum(a(),n)，表示求数组 a 中前 n 个元素的和，则递归表达式为：sum(a(),n)=sum(a(),n-1)+a(n)，当 n=1 时，sum(a

(),1)=a(1)，递归函数如下：

PrivateFunctionsum(a()AsInteger,ByValnAsInteger)AsInteger

Ifn=1Then

sum = a(1)

Else

sum =sum(a,n-1)+ a(n)

EndIf

EndFunction

【例 7 】用递归算法求数组中所有数的最大值。

分析：要求出数组中所有数的最大值，若能求出前 n-1 个数的最大值（假设数组中共有 n 个数），则再与第 n 个数比较，即可得到最大值，同样的要求出前 n-1 个数的最大值，则只要求出前 n-2 个数的最大值，再与第 n-1 个数比较，如此下去，当 n=1 时，最大值就是本身，递归结束。

可以定义一个递归函数 max(a(),n)，表示求数组 a 中前 n 个数的最大值，则 max(a(),n)=max(a(),n-1)与 a(n)的比较，若 a(n)>max(a(),n-1),则max=a(n)，否则 max=max(a(),n-1)，递归函数如下：

PrivateFunction M ax(a()AsInteger,ByValnAsInteger)AsInteger

Ifn=1Then

M ax= a(1)

Else

M ax= M ax(a,n-1)

Ifa(n)> M axThen M ax= a(n)

EndIf

EndFunction

【例 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,posAsInteger

Dim tempAsInteger

Ifn>1Then

Callsort(a,n-1)

Fori=1Ton-1' 找插入位置

Ifa(n)>= a(i)Then

ExitFor

EndIf

Nexti

pos=i

temp= a(n)