吞吴

前几天我们在讨论递归的过程中发现，递归在解决某些问题的时候使得我们思考的方式得以简化，代码也更加精炼，容易阅读。那么既然递归有这么多的优点，我们是不是什么问题都要用递归来解决呢？难道递归就没有缺点吗？今天我们就来讨论一下递归的不足之处。

我们知道，递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。

这样，我们发现，同一个问题，如果递归解决方案的复杂度不明显优于其它解决方案的话，那么使用递归是不划算的。因为它的很多时间浪费在对函数调用的处理上。在C++中引入了内联函数的概念，其实就是为了避免简单函数内部语句的执行时间小于函数调用的时间而造成效率降低的情况出现。在这里也是一个道理，如果过多的时间用于了函数调用的处理，那么效率显然高不起来。

举例来说，对于求阶乘的函数来说，其迭代算法的时间复杂度为O(n)：

而其递归函数的时间复杂度也是O(n)：

但是递归算法要进行n次函数调用，而迭代算法则只需要进行n次迭代而已。其效率上的差异是很显著的。

我们再来看看之前我们讨论的费波纳契数列问题。

我们当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。

那么计算费波纳契数列是否有更好的递归算法呢？ 当然有。让我们来观察一下费波纳契数列的前几项：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

注意到没有，如果我们去掉前面一项，得到的数列依然满足f(n) = f(n-1) – f(n-2), (n>2)，而我们得到的数列是以1，2开头的。很容易发现这个数列的第n-1项就是原数列的第n项。怎么样，知道我们该怎么设计算法了吧？我们可以写这样的一个函数，它接受三个参数，前两个是数列的开头两项，第三个是我们想求的以前两个参数开头的数列的第几项。

在函数内部我们先检查n的值，如果n为3则我们只需返回a+b即可，这是简单情境。如果n>3，那么我们就调用f(b, a+b, n-1)，这样我们就缩小了问题的规模（从求第n项变成求第n-1项）。好了，最终代码如下：

这样得到的算法复杂度是O(n)的。已经是线性的了。它的效率已经可以与迭代算法的效率相比了，但由于还是要反复的进行函数调用，还是不够经济。

由以上分析我们可以看到，递归在处理问题时要反复调用函数，这增大了它的空间和时间开销，所以在使用迭代可以很容易解决的问题中，使用递归虽然可以简化思维过程，但效率上并不合算。效率和开销问题是递归最大的缺点。

虽然有这样的缺点，但是递归的力量仍然是巨大而不可忽视的，因为有些问题使用迭代算法是很难甚至无法解决的（比如汉诺塔问题）。这时递归的作用就显示出来了。

递归的效率问题暂时讨论到这里。

昨天说了一些递归的简单应用，今天再说一点其他的应用吧。

不得不提的一个经典的问题是汉诺塔问题。问题是这样的：

有三个柱子，其中的一个上面套着八个圆盘，从下到上，圆盘按从大到小的顺序排列。要求把所有圆盘移动到另一个柱子上，并遵循以下规则：

• 一次只能移动一个圆盘
• 圆盘只能套在柱子上
• 小圆盘只能放在比它大的圆盘上

要解决这个问题，用普通的方法来作实在是很困难。而用递归来解决呢？ 会不会有一个容易的解决方案呢？

还是考虑递归的两个条件，是否可把问题规模缩小，是否存在简单情境。为了便于讨论，我们把圆盘现在所在的柱子称为源，把圆盘要移动到的柱子成为目的，另外一个柱子称为辅助。我们容易发现，要把最大的圆盘移动到目的，首先要把上面较小的七个圆盘移动到辅助上（注意，这是一个与原问题有着相同的形式且规模更小的问题），然后把大圆盘移动到目的上，在把七个较小圆盘从辅助移动到目的。可以看到，移动七个小圆盘其实与原问题形式相同而规模更小。好了，我们已经成功地缩小了问题规模。下面来找找简单情境。

很容易看到，当只有一个圆盘时，只要把它从源移动到目的就行了。这就是简单情境。

好，两个条件都具备了，我们可以开始写程序了。

以上就是实现输出汉诺塔问题解的主要函数了。你可以编写一个主程序来调用它们。像这样：

不错吧，很简洁的，几行代码，就解决了这个问题。是不是很爽呢？不过这个递归调用的算法的复杂性如何呢？让我们来看看。

记规模为n的输入耗时T(n)，则：
[tex]T(1) = 1[/tex]
[tex]T(n) = 2*T(n-1) + 1[/tex]
[tex]T(n) + 1= 2*(T(n-1) + 1)[/tex]
[tex]T(n) + 1 = (T(1) + 1) * ( 1 – (T(1)+1)^n) / ( 1 – (T(1)+1))[/tex]
[tex]T(n) = 2^n – 1[/tex]

啊，指数级，好像效率不太高啊。但确实解决了问题。

这是一个很经典的例子，我们来给它改个版，留为今天的作业吧：

所有要求不变，添加如下要求：
圆盘不能从源直接移动到目的。
如何解决此问题？复杂度是多少？

昨天大体上说了一下递归的根本思想和使用递归解决问题的两个条件。今天来看看在解决具体问题的时候如何使用递归。

探测回文：

回文是一种字符串，它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢？

首先我们要考虑使用递归的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

先来看第一点，是否存在一种符合条件的分解。容易发现，如果一个字符串是回文，那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且，我们注意到，一个回文的第一个字符和最后一个字符一定是相同的。所以我们很自然的有这样的方法：先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。 注意，我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。

接着再来看第二点， 这种分解是否存在一种简单情境呢？简单情境在使用递归的时候是必须的，否则你的递归程序可能会进入无止境的调用。对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。

好了，两个条件都满足了，基于以上分析，我们可以很容易的编写出解决回文问题的递归实现方式：

看起来很不错嘛。只有简单的几行代码，非常的简短，就解决了问题。

还有一个典型的例子是对已排序数组的二分查找算法。

现在有一个已经排序好的数组，要在这个数组中查找一个元素，以确定它是否在这个数组中，很一般的想法是顺序检查每个元素，看它是否与待查找元素相同。这个方法很容易想到，但它的效率不能让人满意，它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

还是考虑上面的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？

考虑条件一：我们可以这样想，如果想把问题的规模缩小，我们应该做什么？可以的做法是：我们先确定数组中的某些元素与待查元素不同，然后再在剩下的元素中查找，这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢？ 考虑到我们的数组是已经排序的，我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。

接着考虑条件二：简单情境是什么呢？ 容易发现，如果中值元素和待查元素相等，就可以确定待查元素是否在数组中了，这是一种简单情境，那么它是不是唯一的简单情境呢？ 考虑元素始终不与中值元素相等，那么我们最终可能得到了一个无法再分的小规模的数组，它只有一个元素，那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。

好了，基于以上的分析，我们发现这个问题可以用递归来解决，二分法的代码如下：

这个算法的复杂度是O(logn)的，显然要优于先前提到的朴素的顺序查找法。

好了，今天就说到这里，光看不管用，不如留个练习题您回去做做：

写一个函数dig_sum(int n)，输入一个非负整数，返回组成它的数字之和。如：dig_sum(2007) = 2+0+0+7 = 9。

学C语言的时候老师说递归挺难的，但也是很好用的，同时还是一个合格的程序员必须要掌握的。

从学编程以来对递归的理解就不太深刻。一直就停留在“自己调用自己”的程度上。这其实这只是递归的表象（严格来说连表象都概括得不全面，因为除了“自己调用自己”的递归外，还有交互调用的递归）。而递归的思想远不止这么简单。前些日子看了一本叫《程序设计抽象思想》的书，里面很详细的论述了递归的思想。看后令我颇受启发。所以，我开始写这个关于递归的系列，希望能与同道们一同探讨一下递归的力量。

递归，并不是简单的“自己调用自己”，也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说，递归的思想就是：把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法，就是不断地把问题的规模变小（变成原问题的一半），而新问题与原问题有着相同的解法。

有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易的解决。比如汉诺塔问题。但递归的使用也是有它的劣势的，因为它要进行多层函数调用，所以会消耗很多堆栈空间和函数调用时间。

既然递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题，那么是不是这样的问题都能用递归来解决呢？答案是否定的。并不是所有问题都能用递归来解决。那么什么样的问题可以用递归来解决呢？一般来讲，能用递归来解决的问题必须满足两个条件：

• 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式
• 存在一种简单情境，可以使递归在简单情境下退出

如果一个问题不满足以上两个条件，那么它就不能用递归来解决。

举个例子：

求费波纳契数列的第N项的值。

这是一个经典的问题，说到递归一定要提到这个问题。费波纳契数列这样定义：
f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)
这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的：
1、对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是说规模为n的问题，转化成了规模更小的问题；
2、对于n=0和n=1，存在着简单情境：f(0) = 0, f(1) = 1。

因此，我们可以很容易的写出计算费波纳契数列的第n项的递归程序：

[c]int fib(n){
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return f(n-1) + f(n-2);
}[/c]

注意：在编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归，否则，你的函数可能会永不停息的在那里递归调用，你就成了造出第一个永动机的人了。

（未完待续

约瑟夫问题：编号为1，2，3，……，n的n个人按顺时针方向围坐一圈。任选两个正整数作为报数下限s和报数上限m，从第一个人开始按顺时针方向自s开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从s报数，如此下去，直至所有人全部出列为止。设计程序输出出列顺序。

我使用链表实现的方式是：使用无表头循环链表，该链表支持插入和删除操作。使用循环模拟报数，删除报数的节点，将指针指向下一个节点，继续模拟报数，直至链表中无节点为止。

代码如下：
[c]/*
* 约色夫环问题。
*/

#include
#include

#define MSG_ENTER “Please enter the number of persons in the circle:
”
#define MSG_NOW “The circle now is like this:
”
#define MSG_NUMBER “Please enter the start and stop number in order:
”
#define MSG_ERROR “Error: Stop number must be greater than the start number!
”

/* 节点数据结构 */
struct player{
int key;
struct player * next;
};

typedef struct player person;

person * new_person(int key);
person * insert(person * list, person *p);
person * delete(person * ptr);

int main(){
person * list = NULL;
person * p;
int num, start, stop, step, i;

printf(MSG_ENTER);
scanf(“%d”, &num);

p = new_person(1);
list = insert(list, p);
for(i = 0; i next != list){
printf(“%d “, p->key);
p = p->next;
}
printf(“%d
“, p->key);

printf(MSG_NUMBER);
scanf(“%d %d”, &start, &stop);
printf(“Start from : %d; Stop at: %d
“, start, stop);
step = stop – start;
if(step next != p){
for(i = 0; i next;
}
p = delete(p);
}
delete(p);
/* The game ends */

return 0;
}

person * new_person(int key){
person * p = malloc(sizeof(person));
p->key = key;
p->next = NULL;
return p;
}
person* insert(person * list, person * p){
if(list == NULL){
list = p;
list->next = list;
}else{
p->next = list->next;
list->next = p;
}
return list;
}
person * delete(person * ptr){
person * tmp = ptr->next;
person * r = tmp->next;
printf(“%d is out.
“, tmp->key);
ptr->next = tmp->next;
free(tmp);
return r;
}[/c]

定义：算法是一组完成特定任务的有穷指令序列。

一个算法 具有以下性质：

1. 输入：算法有零个或多个输入；
2. 输出：算法有一个或多个输出；
3. 确定性：算法的每一个操作指令都是确定的，有明确的语义，无岐义；
4. 有限性：算法的任何执行路线都能在有限步内结束；
5. 有效性：每一条指令都是足够简单的，原则上用纸和笔就可以处理这条指令。同时指令必须是可行的。

算法可以有任意个输入，但至少要有一个输出（当然，这里的输出并不是指输出到屏幕）。

算法的每一个操作都应该是确定无岐义的，比如我说“把杯子放在碗的旁边” ，这个操作就不是确定的，因为不知道是把杯子放在碗的左边还是右边，而“把杯子倒扣着放在碗的里边”就是确定的。

算法必需有限，如果无限，根本就不能“完成特定任务”了，也就不是算法了。

算法的每一个操作都必需有效，这是显然的。比如“把5除以0的余数输出到屏幕”这个操作就是无效的，因为5除以0是没有意义的。