算法系列之十五：循环和递归在算法中的应用

ldb19890624

浏览: 243678 次
性别:
来自: 北京

最近访客更多访客>>

caizi12

missing1314521

u012363178

halfsking

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (632)

社区版块

存档分类

一、递归和循环的关系

1、递归的定义

顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构，这三种控制结构构成了千姿百态的算法，程序，乃至整个软件世界。递归也算是一种程序控制结构，但是普遍被认为不是基本控制结构，因为递归结构在一般情况下都可以用精心设计的循环结构替换，因此可以说，递归就是一种特殊的循环结构。因为递归方法会直接或间接调用自身算法，因此是一种比迭代循环更强大的循环结构。

2、递归和循环实现的差异

循环（迭代循环）结构通常用在线性问题的求解，比如多项式求和，为某一结果的精度进行的线性迭代等等。一个典型的循环结构通常包含四个组成部分：初始化部分，循环条件部分，循环体部分以及迭代部分。以下代码就是用循环结构求解阶乘的例子：

86/*循环算法计算小数字的阶乘, 0 <= n < 10 */

87int CalcFactorial(int n)

88{

89 int result = 1;

91 int i;

92 for(i = 1; i <= n; i++)

93 {

94 result = result * i;

95 }

97 return result;

98}

递归方法通常分为两个部分：递归关系和递归终止条件（最小问题的解）。递归方法的关键是确定递归定义和递归终止条件，递归定义就是对问题分解，是指向递归终止条件转化的规则，而递归终止条件通常就是得出最小问题的解。递归结构与人类解决问题的方式类似，算法简洁且易于理解，用较少的步骤就能描述解题的全过程。递归方法的结构中还隐含了一个步骤，就是“回溯”，对于需要“先进后出”结构进行操作时，使用递归方法会更高效。以下代码就是用递归方法求解阶乘的例子：

100/*递归算法计算小数字的阶乘, 0 <= n < 10 */
101int CalcFactorial(int n)
102{
103 if(n == 0) /*最小问题的解，也就是递归终止条件*/
104  return 1;
105
106 return n * CalcFactorial(n - 1); /*递归定义*/
107}

从上面两个例子可以看出：递归结构算法代码结构简洁清晰，可读性强，非常符合“代码就是文档”的软件设计哲学。但是递归方法的缺点也很明显：运行效率低，对存储空间的占用也比迭代循环方法多。递归方法通过嵌套调用自身达到循环的目的，函数调用引起的参数入栈等开销会降低算法效率，同样，对存储空间的占用也体现在入栈参数以及局部变量所占用的栈空间。正因为这两点，递归方法的应用以及解题的规模都受系统任务或线程栈空间大小的影响，在一些嵌入式系统中，任务或线程的栈空间只有几千个字节，在设计算法上要慎用递归结构算法，否则很容易导致栈溢出而系统崩溃。

3、滥用递归的一个例子

关于使用递归方法导致栈溢出的例子有很多，网上流传一个判断积偶数的例子，本人已经不记得具体内容了，只记得大致是这样的：

115/*从网上摘抄的某人写的判断积偶数的代码，使用了递归算法*/
116bool IsEvenNumber(int n)
117{
118 if(n >= 2)
119  return IsEvenNumber(n - 2);
120 else
121 {
122  if(n == 0)
123   return true;
124  else
125   return false;
126 }
127}

据说这个例子是某个系统中真是存在的代码，它经受住了最初的测试并被发布出去，当用户的数据大到一定的规模时崩溃了。本人在Windows系统上做过测试，当n超过12000的时候就会导致栈溢出，本系列的下一篇文章，会有一个有关Windows系统上栈空间的有趣话题，这里不再赘述。下面就是一个合理的、中规中矩的实现：

109bool IsEvenNumber(int n)
110{
111 return ((n % 2) == 0);
112}

二、递归还是循环？这是个问题

1、一个简单的24点程序

下面本文将通过两个题目实例，分别给出用递归方法和循环方法的解决方案以及解题思路，便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题（为了简化问题，我们假设只使用求和计算方法）：

从1－9中任选四个数字（数字可以有重复），使四个数字的和刚好是24。

题目很简单，数字都是个位数，可以重复且之用加法，循环算法的核心就是使用四重循环穷举所有的数字组合，对每一个数字组合进行求和，判断是否是24。使用循环的版本可能是这个样子：

8const unsigned int NUMBER_COUNT = 4; //9
9const int NUM_MIN_VALUE = 1;
10const int NUM_MAX_VALUE = 9;
11const unsigned int FULL_NUMBER_VALUE = 24;//45;

40void PrintAllSResult(void)
41{
int i,j,k,l;
int numbers[NUMBER_COUNT] = { 0 };
44
for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++)
{
numbers[0] = i; /*确定第一个数字*/
for(j = NUM_MIN_VALUE; j <= NUM_MAX_VALUE; j++)
{
 numbers[1] = j; /*确定第二个数字*/
 for(k = NUM_MIN_VALUE; k <= NUM_MAX_VALUE; k++)
 {
  numbers[2] = k; /*确定第三个数字*/
  for(l = NUM_MIN_VALUE; l <= NUM_MAX_VALUE; l++)
  {
   numbers[3] = l; /*确定第四个数字*/
   if(CalcNumbersSum(numbers, NUMBER_COUNT) == FULL_NUMBER_VALUE)
   {
    PrintNumbers(numbers, NUMBER_COUNT);
   }
  }
 }
}
}
65}

这个PrintAllSResult()函数看起来中规中矩，但是本人的编码习惯很少在一个函数中使用超过两重的循环，更何况，如果题目修改一下，改成9个数字求和是45的组合序列，就要使用9重循环，这将使PrintAllSResult()函数变成臭不可闻的垃圾代码。

现在看看如何用递归方法解决这个问题。递归方法的解题思路就是对题目规模进行分解，将四个数字的求和变成三个数字的求和，两个数字的求和，当最终变成一个数字时，就达到了递归终止条件。这个题目的递归解法非常优雅：

67void EnumNumbers(int *numbers, int level, int total)
68{
69 int i;
70
71 for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++)
72 {
73  numbers[level] = i;
74  if(level == (NUMBER_COUNT - 1))
75  {
76   if(i == total)
77   {
78    PrintNumbers(numbers, NUMBER_COUNT);
79   }
80  }
81  else
82  {
83   EnumNumbers(numbers, level + 1, total - i);
84  }
85 }
86}
87
88void PrintAllSResult2(void)
89{
90 int numbers[NUMBER_COUNT] = { 0 };
91
92 EnumNumbers(numbers, 0, FULL_NUMBER_VALUE);
93}

如果题目改成“9个数字求和是45的组合序列”，只需将NUMBER_COUNT的值改成9，FULL_NUMBER_VALUE的值改成45即可，算法主体部分不需做任何修改。

2、单链表逆序

第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，但是如果面试者使用了额外的节点存储空间做中转，会得到一个比较低的分数。如何在不使用额外存储节点的情况下使一个单链表的所有节点逆序？我们先用迭代循环的思想来分析这个问题，链表的初始状态如图（1）所示：

图（1）初始状态

初始状态，prev是NULL，head指向当前的头节点A，next指向A节点的下一个节点B。首先从A节点开始逆序，将A节点的next指针指向prev，因为prev的当前值是NULL，所以A节点就从链表中脱离出来了，然后移动head和next指针，使它们分别指向B节点和B的下一个节点C（因为当前的next已经指向B节点了，因此修改A节点的next指针不会导致链表丢失）。逆向节点A之后，链表的状态如图（2）所示：

图（2）经过第一次迭代后的状态

从图（1）的初始状态到图（2）状态共做了四个操作，这四个操作的伪代码如下：

head->next = prev;

prev = head;

head = next;

next = head->next;

这四行伪代码就是循环算法的迭代体了，现在用这个迭代体对图（2）的状态再进行一轮迭代，就得到了图（3）的状态：

图（3）经过第二次迭代后的状态

那么循环终止条件呢？现在对图（3）的状态再迭代一次得到图（4）的状态：

图（4）经过第三次迭代后的状态

此时可以看出，在图（4）的基础上再进行一次迭代就可以完成链表的逆序，因此循环迭代的终止条件就是当前的head指针是NULL。

现在来总结一下，循环的初始条件是：

prev = NULL;

循环迭代体是：

next = head->next;

head->next = prev;

prev = head;

head = next;

循环终止条件是：

head == NULL

根据以上分析结果，逆序单链表的循环算法如下所示：

61LINK_NODE *ReverseLink(LINK_NODE *head)
62{
63 LINK_NODE *next;
64 LINK_NODE *prev = NULL;
65
66 while(head != NULL)
67 {
68  next = head->next;
69  head->next = prev;
70  prev = head;
71  head = next;
72 }
73
74 return prev;
75}

现在，我们用递归的思想来分析这个问题。先假设有这样一个函数，可以将以head为头节点的单链表逆序，并返回新的头节点指针，应该是这个样子：

77LINK_NODE *ReverseLink2(LINK_NODE *head)

现在利用ReverseLink2()对问题进行求解，将链表分为当前表头节点和其余节点，递归的思想就是，先将当前的表头节点从链表中拆出来，然后对剩余的节点进行逆序，最后将当前的表头节点连接到新链表的尾部。第一次递归调用ReverseLink2(head->next)函数时的状态如图（5）所示：

图（5）第一次递归状态图

这里边的关键点是头节点head的下一个节点head->next将是逆序后的新链表的尾节点，也就是说，被摘除的头接点head需要被连接到head->next才能完成整个链表的逆序，递归算法的核心就是一下几行代码：

newHead = ReverseLink2(head->next); /*递归部分*/
head->next->next = head; /*回朔部分*/
head->next = NULL;

现在顺着这个思路再进行一次递归，就得到第二次递归的状态图：

图（6）第二次递归状态图

再进行一次递归分析，就能清楚地看到递归终止条件了：

图（7）第三次递归状态图

递归终止条件就是链表只剩一个节点时直接返回这个节点的指针。可以看出这个算法的核心其实是在回朔部分，递归的目的是遍历到链表的尾节点，然后通过逐级回朔将节点的next指针翻转过来。递归算法的完整代码如下：

77LINK_NODE *ReverseLink2(LINK_NODE *head)
78{
79 LINK_NODE *newHead;
80
81 if((head == NULL) || (head->next == NULL))
82  return head;
83
84 newHead = ReverseLink2(head->next); /*递归部分*/
85 head->next->next = head; /*回朔部分*/
86 head->next = NULL;
87
88 return newHead;
89}