汉诺塔的递归和非递归实现

非递归的例子使用了模拟程序调用栈的方法，整个执行流程其实和递归的例子基本上一致。但非递归代码理解起来会困难不少，不过代码中有注释，可以帮助你更好的理解非递归的代码。

递归实现

static void hanoi_recursive(int n, char from, char to, char via) {
    if (n == 1) {
        printf("%c -> %c\n", from, to);
        return;
    }
    hanoi(n-1, from, via, to);  // 将n-1个盘子从from移动到via
    hanoi(1, from, to, via);    // 将最底下的盘子从from移动到to
    hanoi(n-1, via, to, from);  // 将n-1个盘子从via移动到to
}

非递归实现

#define call(...) ({ *(++top) = (frame_t){.pc = 0, __VA_ARGS__}; })
#define ret() ({ top--; })
#define goto(loc) ({ f->pc = (loc)-1; })

typedef struct {
    int pc, n;
    char from, to, via;
} frame_t;

/*
 * 这里模拟了程序栈的调用。
 * 这里比较关键的是理解`pc`的含义：
 *      1. 新栈顶第1次会匹配`case 0`的分支，此时栈顶的pc++
 *      2. 然后匹配`case 1`， 创建1个栈帧入栈，pc=0，
 *      3. 前一个栈帧的pc++，更新pc的目的是因为:
 *         当从这里往后产生的所有栈帧都返回了，通过更新这个pc值可以将代码向下一个状态转移
 *      4. 更新栈顶top变量
 *      5. 重复过程1，直到新栈帧的n==1，表明到达了递归的终止条件
 *      6. 跳转到`ret()`，并且更新栈顶top变量
 */
static void hanoi(int n, char from, char to, char via) {
    frame_t stk[64], *top = stk - 1;

    call(n, from, to, via);

    for (frame_t *f; (f = top) >= stk; f->pc++) {
        switch (f->pc) {
        case 0:
            if (f->n == 1) {
                printf("%c -> %c\n", f->from, f->to);
                goto(4);
            }
            break;

        case 1:
            call(f->n - 1, f->from, f->via, f->to);
            break;

        case 2:
            call(1, f->from, f->to, f->via);
            break;

        case 3:
            call(f->n - 1, f->via, f->to, f->from);
            break;

        case 4:
            ret();
            break;

        default:
            assert(0);
        }
    }
}

测试代码

#include <stdio.h>
#include <assert.h>

int main(int argc, char *argv[]) {
    hanoi_recursive(3, 'a', 'b', 'c');

    printf("===================\n");

    hanoi(3, 'a', 'b', 'c');
    return 0;
}