递归算法应用分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇递归算法应用分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：递归算法是程序设计中一种重要的方法，对于一些看起来很复杂的问题，使用递归方法可以提供非常优雅和简洁的解决方案，而且解题思路清晰、代码量小。但是递归算法的设计有几个需要注意的关键点，如果不能很好的解决，则无法在程序设计中体现递归的强大功能。该文通过两个示例说明设计递归算法中需要关注的关键点及其解决办法。
关键词：算法；递归；返回值；参数
中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)28-0107-04
Analysis of JUnit Framework
DAI Jian-guo,CAO Chuan-dong, GUO Li
(College of Information Science and Technology,Shihezi University,Shihezi 832000,China)
Abstract: Recresive Algorithm is an important technology in programming, To some complicated problem, we could get very elegant solution with less amounts of codes by using recursive algorithm. There are several key points in recursive algorithm designation which must solve, the paper explains the key points and the solutions with two examples.
Keywords: algorithm; recursive; return value; parameter
1 引言
递归算法是程序设计中比较难以掌握的技术，其中包含的设计思想非常巧妙，在数据结构的课程中有很多算法都用到了递归的方法，比如著名的汉诺塔问题就是一个非常经典的例子，还有二叉树的遍历、快速排序等等。但是递归算法的设计比较困难，甚至有的问题简直无法用递归去解决，关键在于是否掌握了递归算法的核心思想。递归算法的核心在于三个方面：首先，合理的分析问题，采用将大问题采用分而治之的思想，就是大规模的问题合理地分成几个类型相同的但是规模稍微小一点儿的问题，直至到达我们能够解决的程度；其次，分析如果问题到达能够解决的程度后应该怎么解决，也就是递归该怎么返回的问题；最后，参数的传递，当前的状态是否需要保存到下一层递归，如果需要，该如何传递。如果能够解决好这样三个问题，就是把握好了设计递归算法的关键点，设计就有章可循。下面通过两个例子说明设计递归算法的三个关键点。
2 划分问题
合理的划分问题是在程序设计中应用递归算法的第一步，如果不能做好这一步工作，其余都免谈。有的问题划分比较容易，可以看到非常清晰的划分方法，比如汉诺塔，在分析过程中可以非常清晰的看到大问题一步步分解成小问题的过程。但是有的问题就比较麻烦，这个过程并不清晰。比如这样一个例子：使用递归算法实现不带表头结点单链表的逆序。首先看一下不带表头结点单链表逆序的非递归实现方法，逆序的过程如图1所示，其中L表示指向单链表第一个结点的指针，p和q表示在逆序过程中用的临时指针变量。
其中结点定义如下：
typedef struct Node{
datatype data;
struct Node *next;
} Node, *Linklist;
逆序的代码如下：
void reverse(Linklist *L){
if(!(*L) || !(*L)->next)// 如果是空链表或者只有一个结点的单链表，直接返回
return;
Linklist p, q;
p = (*L)->next;
while(p){
q = p->next;
p->next = *L;
*L = p;
p = q;
} }
通过整个求解过程可以发现，算法并不复杂，但如果要用递归不好下手，看不见清晰的可以把大的问题划分成小问题的方法。下面我们换一个思路想一想。把整个链表分为两个部分：第一个结点和其余所有结点组成的单链表（假设为L1），所谓逆序就是如下的过程：
1) 把L1逆序
2) 第一个结点放在逆序后的L1的最后一个结点的后面
3) 使用同样的方法对L1逆序
这就是一个递归的过程。同样设函数名为reverse(Linklise L)，算法描述如下：
输入：待逆序链表的第一个结点
输出：逆序后链表的最后一个结点
Begin
p := L;
q := L->next;
q := reverse(q)
q->next := p;
p->next := 0;
End
reverse方法返回链表逆序后的最后一个结点。问题划分清楚后，那么现在进入递归算法设计的第二步：什么时候返回?
3 递归的返回
递归一定要有返回，否则就是无穷递归。那递归该什么时候返回呢？当问题细分到可以解决的程度时，递归就可以返回了，对于我们这个问题，规模有多大的时候可以解决呢？答案很明确，就是当L1中只有一个结点的时候，逆序不用做任何事情，而且逆序后的最后一个结点就是这唯一的一个结点。代码大致如下：
if(!L || !L->next)// 如果是空链表或者只有一个结点的单链表，直接返回该结点
return L;
下面是完整的代码：
Linklist LL;
Linklist reverse(Linklist L){
Linklist p, q;
if(!L || !L->next){// 如果是空链表或者只有一个结点的单链表，直接返回该结点
LL = L;// LL为全局变量
return L;
}
p = L;
q = L->next;
q = reverse(q);
q->next = p;
p->next = 0;
return p;
}
由于在递归的最后一层返回时，返回的是逆序后的链表的最后一个结点的指针，链表的第一个结点丢失，所以在实现过程中用了一个全局变量LL，用于取得链表逆序后的第一个结点，也就是最深层递归函数返回的结点。
4 参数的传递
在递归的运行过程中，当由当前层进入更深层的函数调用时，需要保存当前的状态，也就是将当前所使用的资源入栈[1]。临时变量入栈不需要我们做什么工作，但如果使用了外部资源，并且外部资源的状态会影响程序的运行时，就必须要在递归函数中做外部资源复制与传递的工作。下面是一个例子：dreamzk 种了3种花 A、B、C 各 a、b、c 盆，每天他都会把这些花搬到外面给他们晒晒太阳，但是他想把这些花摆放得有特色点，于是要求任意相邻的两盆花不能相同，一共有多少中摆放方式呢？请你帮他算算。
4.1 问题分析
这个问题可以采用典型的“分而治之”的思想，第一盆花有三种摆放方式：1) 第一盆是A；2) 第一盆是B；3.第一盆是C，分别用RankA、RankB、RankC代表每一种情况的摆放方式的总数，那么总的排放方式为：RankA+RankB+RankC，这样就把总问题分解成为三个小问题。现在的问题是：RankA、RankB、RankC是多少？这三者的求解具有相似性，只需要分析一个即可，下面以RankA为例进行分析。RankA表示第一盆选择的是A的情况下一共有多少种摆放方式，第一盆既然已经固定了，那么现在的问题成了：一共有三种花A、B、C 各 a-1、b、c 盆，第一盆只能放B或C，一共有多少种摆放方式。继续用RankB、RankC代表两种情况摆放方式的总数，则可以得到总的摆放数量是RankB+RankC，只是问题规模缩小了，然后继续可以分解缩小了规模的RankB和RankC，直至可以解决问题。但是还有两个问题：
1) 如果某一种花摆放完毕只剩下两种花怎么办？那只能两种花交替放；
2) 如果只剩下了一种花怎么办？如果剩下的一种花的数量大于了1，则这种摆放方式不成功，返回0，如果等于1，并且与前一种花不一样，说明这是一次成功的摆放，返回1；
4.2 准备
在编程实现之前需要将问题域用计算机可以处理的方式描述出来，这里的问题是，怎样描述花的种类和数量，可以采用一个长度为4的一维数组，第0位空着，第一位中存储的数字代表第一种花的数量，依次类推。数组中的内容代表每一次递归调用时的状态，也就是每一种花有多少，所以每一次递归调用的数组必须入栈，但是数组作为参数时传递的是指针，而不是复制数组然后传递副本，所以这个工作需要编程实现，代码如下：其中a代表源数组，b代表目标数组。
void copy_arr(int a[4], int b[4]){
for(int i = 1; i < 4; i++){
b[i] = a[i];
} }
4.3 实现
根据前面的分析可以得到，问题一共有三种状态：1) 有三种花可以摆放；2) 只有两种花可以摆放；3) 只剩下一种花摆放。并且当前摆放的选择受到前一盆花的限制，下面一一分析。对于第一种情况，假设前一盆花摆放的是A，算法如下：
输入：（1）前一盆花的种类（2）剩下两盆花的种类（3）当前各种花的数量
输出：当前状态下符合题目要求的摆放方式的数量
步骤1. A种花的数量减一。
步骤2. 当前只能摆放B或者C，如果B的数量为0（已经摆放完了），则当前只能摆放C，如果C的数量为0，则当前只能摆放B，在这两种情况下问题都退化成为第二种状态，也就是两种花的摆放。
步骤3. 否则（也就是B和C都不为0），那么总的可以摆放的方式就是当前摆放B和C两种方式的和，也就是问题分解为规模小一些的两个同类问题
具体代码如下，其中pre表示前一种花的序号，x和y分别表示可以摆放的另外两种花的序号，flowers表示现有三种花的数量数组。
int rank_three(int pre, int x, int y, int flowers[4]){
int new_arr[4];
copy_arr(flowers, new_arr);
new_arr[pre]--;
if(new_arr[x] == 0)
return rank_two(y, pre, new_arr);
else if(new_arr[y] == 0)
return rank_two(x, pre, new_arr);
return rank_three(x, pre, y, new_arr) + rank_three(y, x, pre, new_arr);
}
对于第二种情况，假设只剩下A和B两种花，并且前一盆花摆放的是A，算法如下：
输入：（1）前一盆花的种类（2）剩下一盆花的种类（3）当前各种花的数量
输出：当前状态下符合题目要求的摆放方式的数量
步骤1. A种花的数量减一。
步骤2. 当前只能摆放B，如果B的数量为0（已经摆放完了），则问题退化成为第一种状态，也就是一种花的摆放。
步骤3. 否则（也就是B不为0），那么当前位置摆放B，问题转变成为规模小一些的同类问题。
具体代码如下，其中pre表示前一种花的序号，pos表示可以摆放的另外一种花的序号，flowers表示现有三种花的数量数组。
int rank_two(int pre, int pos, int flowers[4]){
int new_arr[4];
copy_arr(flowers, new_arr);
new_arr[pre]--;
if(new_arr[pos] == 0)
return rank_one(pre, new_arr);
return rank_two(pos, pre, new_arr);
}
对于第三种情况，假设前一盆花是A，那么现在也只能摆放A，因为另外两种花都摆放完了，所以算法如下：
输入：（1）前一盆花的种类（2）当前各种花的数量
输出：当前状态下符合题目要求的摆放方式的数量
步骤1. 如果A的数量不为0，前一盆是A，现在也只能摆放A，说明已经无法完成题目的要求，这种摆放方式不符合题目要求，返回0。
步骤2. 否则，如果A的数量为0，说明所有的花都按照要求摆放完毕，这是一次合乎要求的摆放，返回1。
具体代码如下，其中pos表示需要摆放的花的序号，flowers表示现有三种花的数量数组。
int rank_one(int pos, int flowers[4]){
if(flowers[pos] == 0)
return 1;
return 0;
}
总的问题分解为三个第一类问题，就是第一个摆放A、B、C，总的摆放方式为三者之和，代码如下，其中flowers表示初始状态三种花的数量数组。
int rank(int flowers[4]){
return rank_three(1, 2, 3, flowers) + rank_three(2, 1, 3, flowers) + rank_three(3, 1, 2, flowers);
}
至此，通过将大问题不断细分成若干小问题，运用递归方法解决了看似很复杂的问题，在这个题目当中，多次用到了拷贝数组的过程，这是由于数组当作参数传递时，传递的是指针，并没有做数组的复制，在这个题目当中每一次递归的调用都必须拥有一份独立的当前各种花的数量数组的拷贝，所以在每一次修改花的数量之前都要做数组的拷贝工作。做好参数的传递，这是在设计递归算法时需要考虑的重要步骤之一。
5 结束语
使用递归算法可以解决一些看起来非常复杂、无从下手的问题，虽然参考文献[3]和[4]提及了递归算法的时间和空间效率问题，提出了递归算法的非递归解决方案，但是随着计算机硬件的发展，在很多软件开发过程中并不在乎那一点点效率损失，而编程的简洁性成为更重要的一个方面[2]，此时是递归算法一展身手的机会，好的递归算法设计非常精巧，可以用很少的代码解决复杂的问题，递归算法的设计通常比较困难，但也是有章可循，通过把握住设计过程的三个关键问题，能够使这一强大工具在程序设计中更好的发挥作用。本文创新点在于对递归算法设计的关键技术进行了总结,并通过示例加以说明。
参考文献：
[1] 岳爱菊,杜海涛.浅析递归和递推[J].山东电大学报,2005(4):27-28.
[2] 刘萍,黄小兰.例析程序设计中的递归算法[J].青海师专学报,2007(5):118-121.
[3] 王t,郭芳侠,王振邦.递归问题的非递归算法及效率分析[J].陕西师范大学学报学报,2005,1(33):63-65.
[4] 陈燕晖,邢晶,罗宇.一种消除递归的新方法[J].计算机工程与应用,2006(4):73-75.
[5] 王晓剑,王安民,孟宪君,等.递归在故障诊断专家系统设计中的应用[J].微计算机信息,2008,1-1:154-156.