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。

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

用堆栈模拟递归求和

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

我们注意到，递归时的堆栈有两个需要记录的变量，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
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=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
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=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倍。

首页   •   教程   •   使用堆栈模拟递归完成汉诺塔步骤求解
arrow_back 上一篇
解决 h5ai 在32位PHP环境下无法显示超过2GB文件的问题

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