前言
有如下汉诺塔步骤求解代码:
#include <stdio.h>
int sum = 0;
void move(int n, char from, char to){
sum++;
printf("Step %d, Move disk %d %c --> %c\n", sum, n, from, to);
}
void hanoi(int n, char A, char B, char C) {
// 若只有一个元素,直接把这个元素移动到C
if (n == 1) {
move(n, A, C);
} else {
// 否则把前n-1个元素,借助C移动到B
hanoi(n - 1, A, C, B);
// 再把A最下面的元素移动到C
move(n, A, C);
// 最后把B上的元素借助A移动到C
hanoi(n - 1, B, A, C);
}
}
int main() {
int n;
printf("Input disks: ");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
printf("\nTotal steps: %d", sum);
return 0;
}
这是一个典型的递归求解代码。我们知道,使用递归就是一个函数调用自身,在递归调用的过程当中,系统会为每一层的返回点、局部量等开辟了栈来存储。递归的实质就是系统不断压栈又出栈的过程。也正因此,在调用递归次数过多时会造成“堆栈溢出”的错误,但如果我们使用数据结构中的栈结构手动模拟递归的压栈,出栈过程,可以避免出现堆栈溢出。
那么,要如何做到模拟递归的压栈,出栈过程呢?
先从求和算法说起
递归求和
这是一个用递归计算1+2+3+...+n
的和的算法:
long sum(long n) {
if (n == 1) {
return 1;
} else {
return n + sum(n - 1);
}
}
假设我们调用sum(10)
进行求值,程序势必要先求得sum(9)
的值,在sum(9)
返回值前,程序会先将sum(10)
的状态压栈。而要求sum(9)
的值,程序又要先求得sum(8)
的值……如此进行(压栈)下去,直到程序调用到sum(1)
,函数返回值1
,完成了第一次出栈。接下来程序会依次返回计算的值(出栈),一直返回到sum(10)
,将sum(10)
最终的计算结果,返回给调用sum(10)
的位置。
下面用一个表格表示堆栈,展示这一过程:
第一次调用(压栈)
N SUM 10 10+?
第二次调用(压栈)
N SUM 10 10+? 9 9+?
……
第十次调用(压栈)
N SUM 10 10+? 9 9+? ... ... 2 2+? 1 ?
此时,根据sum()
函数的定义,传入的值为1
时,函数终于不用再调用自身递归压栈了,而是直接返回一个确切的值1
。于是,开始出栈。
第一次回调(出栈)
N SUM 10 10+? 9 9+? ... ... 2 2+? 11
第二次回调(出栈)
N SUM 10 10+? 9 9+? ... ... 22+111
……
第十次回调(出栈)
N SUM 1010+4599+36... ... 22+111
此时栈空,程序将成功返回sum(10)
的值55
。
以上过程仅作为示意,并不代表程序实际运行时的压栈与出栈过程。
用堆栈模拟递归求和
有了上面的对递归算法的压栈与出栈的分析,下面我们尝试使用堆栈来模拟该递归算法。
我们注意到,递归时的堆栈有两个需要记录的变量,n
与sum
。可定义如下的结构体:
typedef struct Sum {
long n;
long sum;
} Sum;
typedef struct Stack {
Sum *top;
Sum *bottom;
int stack_size;
} Stack;
Sum
结构体即为每一次压栈的数据,Stack
用于操作压栈/出栈操作。
创建操作堆栈的函数,此处参考了严蔚敏主编的《数据结构》一书中的算法:
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
void InitStack(Stack *S) {
S->bottom = (Sum *) malloc(STACK_INIT_SIZE * sizeof(Sum));
if (!S->bottom) {
exit(0);
}
S->top = S->bottom;
S->stack_size = STACK_INIT_SIZE;
}
void Push(Stack *S, Sum e) {
if (S->top - S->bottom >= S->stack_size) {
S->bottom = (Sum *) realloc(S->bottom, (S->stack_size + STACK_INCREMENT) * sizeof(Sum));
if (!S->bottom) {
exit(0);
}
S->top = S->bottom + S->stack_size;
S->stack_size += STACK_INCREMENT;
}
*S->top = e;
*S->top++;
}
void Pop(Stack *S, Sum *e) {
if (S->top == S->bottom) {
return;
}
S->top--;
*e = *S->top;
}
int StackEmpty(Stack S) {
if (S.bottom == S.top) {
return 1;
} else {
return 0;
}
}
若对堆栈操作过程较为熟悉,上述代码并不难理解。事实上,关键的代码应该是如何对压栈与出栈的过程进行模拟。
下面就编写stack_sum()
程序用于模拟压栈、出栈。可参考注释进一步理解压栈与出栈的过程:
long stack_sum(long n) {
// 定义并初始化一个栈
Stack S;
InitStack(&S);
// 当n>=1时,不断压栈
while (n >= 1) {
Sum e = {n, n};
Push(&S, e);
n--;
}
// 压栈完毕后,就进行出栈操作
Sum t;
while (!StackEmpty(S)) {
// 不断出栈,并将出栈后栈内的sum值与上一个栈内的sum值相加,直到栈为空
Pop(&S, &t);
(S.top - 1)->sum += t.sum;
}
// 栈为空(top与bottom指针指向同一个地址,存储的数据并未删除)后,bottom内sum的值即为所得结果
return S.bottom->sum;
}
不难看出,这实际上是一个迭代计算的过程。
使用递归与堆栈的对比
前面说到,直接在函数中使用递归同样是堆栈的过程,但若递归的层数过多会出现堆栈溢出,得不到我们预期的结果。而若手动使用堆栈进行模拟堆栈的操作,由于这一“堆栈”其实是存储在内存空间中的变量,容量比直接调用递归要大,能计算的层数也就更多。
测试发现,在上述的例子中,令n = 200000
,分别调用sum(n)
与stack_sum(n)
,发现sum(n)
不能返回值,在debug
模式下可以看到出现了SIGSEGV (Segmentation fault)
错误,也即发生了堆栈溢出,程序不能对如此多层数的递归调用返回正确的值。而我们用堆栈结构模拟递归的函数stack_sum(n)
返回了正确的值20000100000
。
C语言中递归能够调用的最大层级受到递归的复杂度,运行的环境等因素的影响,C语言本身并没有对此作出限制。在某些环境下n = 200000
时sum(n)
也有可能不发生堆栈溢出,例如在 GDB online Debugger 网站中运行sum(200000)
也可返回正确的结果,说明它的栈空间更大一些。
汉诺塔的递归求解是如何实现的
先回顾一下前面的hanoi()
算法:
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
move(n, A, C);
} else {
hanoi(n - 1, A, C, B);
move(n, A, C);
hanoi(n - 1, B, A, C);
}
}
简而言之,这一算法的思想是:将前 n-1 个元素从A移动到B -> 将最后一个元素n从A移动到C -> 将位于B的前n-1个元素移至C
。
与上面求和的递归不同,这里的算法进行了两次递归调用:hanoi(n - 1, A, C, B)
与hanoi(n - 1, B, A, C)
。这对应了将前 n-1 个元素从A移动到B
与将位于B的前n-1个元素移至C
的算法。既然每一次递归即是一次压栈最后再出栈的过程,那么在压栈与出栈的时候,该如何判断应该压入或者出来的是(n-1 A C B)
还是(n-1 B A C)
?
这两个调用递归的位置最大的区别在于,压入了(n-1 A C B)
并出栈后,会执行一次move(n, A, C)
再压入(n-1 B A C)
。我们可以在栈中增加一个变量move
,用0
与1
表示这个栈的n
是否已经move(n, A, C)
过了,根据此变量判断接下来应该压入的是(n-1 A C B)
还是(n-1 B A C)
。
直白的文字描述可能过于抽象,下面我们以调用hanoi(3, a, b, c)
为例,同样使用表格的形式对栈操作进行示意。
第一次调用(压栈)
n A B C move 3 a b c 0 这时,栈顶
n=3>1
,且move=0
,因此压入(n-1 A C B 0)
直到n=1
,要注意的是这里的A C B
对应的是上一个栈的A C B
对应的值。
由于会出现重复压栈与出栈操作,没有必要标明压栈与出栈次数。
调用(压栈)到
n=1
后
n A B C move 3 a b c 0 2 a c b 0 1 a b c 0
此时n=1
,进行move
和出栈操作
n A B C move 3 a b c 0 2 a c b 0 1abc1累计执行的代码如下所示:
move(1, a, c);
这一步执行完毕后,程序会回调到n=2
的位置
n A B C move 3 a b c 0 2 a c b 1 move(1, a, c); move(2, a, b);
执行
move
后再次压栈,由于又压到了n=1
,又会执行一次move
并出栈:
n A B C move 3 a b c 0 2 a c b 1 1cab1move(1, a, c); move(2, a, b); move(1, c, b);
这时,程序回到n=2
处,发现n=2
已经move
过了,因此n=2
将出栈,对上一个栈(n=3
处)执行move
,并再次入栈
出栈
n A B C move 3 a b c 0 2acb1move(1, a, c); move(2, a, b); move(1, c, b);
回到上一个栈即
n=3
处执行move
,然后压栈直到n=1
n A B C move 3 a b c 1 2 b a c 0 1 b c a 0 move(1, a, c); move(2, a, b); move(1, c, b); move(3, a, c);
注意这里,因为
n=3
的move=1
所以压入(2 B A C 0)
,正因为此n=2
下move=0
,因此之后压入的是(1 A C B 0)
。
同样的,此处n=1
,执行move
并出栈
n A B C move 3 a b c 1 2 b a c 0 1bca1move(1, a, c); move(2, a, b); move(1, c, b); move(3, a, c); move(1, b, a);
回到n=2
后,由于此处move=0
,因此会执行一次move
,再压入(1 B A C 0)
n A B C move 3 a b c 1 2 b a c 1 1 a b c 0 move(1, a, c); move(2, a, b); move(1, c, b); move(3, a, c); move(1, b, a); move(2, b, c);
此处又有n=1
,执行move
然后出栈
n A B C move 3abc12bac11abc1move(1, a, c); move(2, a, b); move(1, c, b); move(3, a, c); move(1, b, a); move(2, b, c); move(1, a, c);
n=1
出栈后,n=2
处move=1
,所以仍然出栈回到上一个栈n=3
;而该处依然有move=1
,于是n=3
也出栈了。
这时,栈为空了,说明所有的步骤我们已经执行完毕,程序退出。
手动堆栈模拟递归求解汉诺塔
按照上述分析思路,我们开始尝试手动堆栈模拟递归求解汉诺塔问题。
同上面的递归求和改用堆栈写一样,我们可以先定义如下的结构体:
typedef struct hanoi {
int n;
char A;
char B;
char C;
int move;
} hanoi;
typedef struct HanoiStack {
hanoi *top;
hanoi *bottom;
int stack_size;
} HanoiStack;
堆栈操作的函数同上,不再赘述。
将改用堆栈求解汉诺塔的函数命名为solve()
,有如下定义
void solve(int n, char A, char B, char C);
第一步自然是先初始化栈空间,并将初始状态入栈。
void solve(int n, char A, char B, char C) {
// 初始化,
HanoiStack S;
InitStack(&S);
// 将初始状态入栈
hanoi t = {n, A, B, C, 0};
Push(&S, t);
......
}
类似于递归中的判断,接下来需要在一个判断栈不为空的循环中,判断栈顶的n
是否为1
,若是,执行move
,出栈等操作;若不是,判断其move
值为何,压入相应的栈。
void solve(int n, char A, char B, char C) {
......
while (!StackEmpty(S)) {
// 获取栈顶元素
GetTop(&S, &t);
if (t.n == 1) {
......
} else if (t.move == 0) {
// 栈顶元素n!=1,move=0的,压入(n-1 A C B 0)
hanoi k = {t.n - 1, t.A, t.C, t.B, 0};
Push(&S, k);
} else {
// move=1的,压入(n-1 B A C 0)
hanoi k = {t.n - 1, t.B, t.A, t.C, 0};
Push(&S, k);
}
}
}
如何进行出栈的操作极为关键。我们知道,n=1
时肯定是要出栈的,而当n=1
出栈后,需要对处于栈顶的元素move
值进行判断,若为0
则执行move
并将其值设为1
,程序继续执行(压栈)。若为1
,则出栈——然后让程序继续执行吗?还是继续判断出栈后栈顶的元素的move
值呢?显然是后者,否则n=3
的move
值永远为0
,程序将重复在n=1
与n=2
之间做压栈与出栈操作。这使得我们想到,我们应该要有一个循环语句执行,确保出栈后继续执行(压栈)时栈顶的元素是经过move
后的元素。
我们使用一个is_loop
变量用于确定是否需要继续判断栈顶的元素情况。
void solve(int n, char A, char B, char C) {
......
int is_loop;
while (!StackEmpty(S)) {
// 获取栈顶元素
GetTop(&S, &t);
if (t.n == 1) {
// 如果栈顶元素n=1,move并出栈
move(t.n, t.A, t.C);
Pop(&S, &t);
// 检测出栈后栈顶的元素是否已move,若未move,move后将move值设置为1
// 若已move,将其出栈,并设置循环flag is_loop=1,让其继续检测栈顶元素的move情况
do {
is_loop = 0;
if (!StackEmpty(S)) {
GetTop(&S, &t);
if (t.move == 0) {
move(t.n, t.A, t.C);
(S.top - 1)->move = 1;
} else {
Pop(&S, &t);
is_loop = 1;
}
}
} while (is_loop);
}
......
}
}
至此,我们的用堆栈模拟汉诺塔递归求解完成了。
递归与用堆栈模拟递归效率对比
无论是递归还是堆栈,两者的算法是一样的,它们的时间复杂度均为O(2^n)
,但因为堆栈使用的是内存空间而非实际的栈空间,效率是比不上直接调用递归的。本地测试发现汉诺塔的个数n
相同,不输出每一步的过程的情况下,堆栈模拟递归所耗时大约是直接递归的7倍。