HBTech's Blog
HBTech's Blog
使用堆栈模拟递归完成汉诺塔步骤求解

前言

有如下汉诺塔步骤求解代码:

#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+?
1 1

第二次回调(出栈)

N SUM
10 10+?
9 9+?
... ...
2 2+1
1 1

……

第十次回调(出栈)

N SUM
10 10+45
9 9+36
... ...
2 2+1
1 1

此时栈空,程序将成功返回sum(10)的值55

以上过程仅作为示意,并不代表程序实际运行时的压栈与出栈过程。

用堆栈模拟递归求和

有了上面的对递归算法的压栈与出栈的分析,下面我们尝试使用堆栈来模拟该递归算法。

我们注意到,递归时的堆栈有两个需要记录的变量,nsum。可定义如下的结构体:

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 = 200000sum(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,用01表示这个栈的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
1 a b c 1

累计执行的代码如下所示:

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
1 c a b 1
move(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
2 a c b 1
move(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=3move=1所以压入(2 B A C 0),正因为此n=2move=0,因此之后压入的是(1 A C B 0)

同样的,此处n=1,执行move并出栈

n A B C move
3 a b c 1
2 b a c 0
1 b c a 1
move(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
3 a b c 1
2 b a c 1
1 a b c 1
move(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=2move=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=3move值永远为0,程序将重复在n=1n=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倍。

HBTech's Blog

使用堆栈模拟递归完成汉诺塔步骤求解
前言 有如下汉诺塔步骤求解代码: #include <stdio.h> int sum = 0; void move(int n, char from, char to){ sum++; printf("Step %d, Move disk %d %c --&…
扫描二维码继续阅读
2021-01-01