C语言编程题使用递归求解汉诺塔问题

1、一般递归解法

最常见的解法，按照经典的递归思路来移动盘子。

#include <stdio.h>

void hanoi(int n, char src, char dest, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", src, dest);
        return;
    }
    hanoi(n - 1, src, aux, dest);
    printf("Move disk %d from %c to %c\n", n, src, dest);
    hanoi(n - 1, aux, dest, src);
}

int main() {
    int n = 3;  // 可以修改n的值测试不同的盘子数
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

2、使用尾递归优化

尾递归可以优化递归调用，减少栈的消耗，不过这个方法在汉诺塔问题中的应用不明显。

#include <stdio.h>

void hanoiTailRec(int n, char src, char dest, char aux, int originalN) {
    if (n == 0) return;

    if (n == 1) {
        printf("Move disk %d from %c to %c\n", originalN, src, dest);
        return;
    }

    hanoiTailRec(n - 1, src, aux, dest, originalN);
    printf("Move disk %d from %c to %c\n", originalN - n + 1, src, dest);
    hanoiTailRec(n - 1, aux, dest, src, originalN);
}

void hanoi(int n, char src, char dest, char aux) {
    hanoiTailRec(n, src, dest, aux, n);
}

int main() {
    int n = 3;
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

3、使用栈模拟递归

通过手动管理一个栈来模拟递归调用，这种方法可以帮助理解递归的工作原理，并且在某些情况下可以优化递归的性能。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int n;
    char src;
    char dest;
    char aux;
    int step;
} Frame;

void hanoiIterative(int n, char src, char dest, char aux) {
    Frame* stack = (Frame*)malloc(n * sizeof(Frame));
    int top = -1;

    stack[++top] = (Frame){n, src, dest, aux, 0};

    while (top >= 0) {
        Frame* f = &stack[top];

        if (f->n == 1 && f->step == 0) {
            printf("Move disk %d from %c to %c\n", f->n, f->src, f->dest);
            top--;
        } else if (f->step == 0) {
            f->step = 1;
            stack[++top] = (Frame){f->n - 1, f->src, f->aux, f->dest, 0};
        } else if (f->step == 1) {
            printf("Move disk %d from %c to %c\n", f->n, f->src, f->dest);
            f->step = 2;
            stack[++top] = (Frame){f->n - 1, f->aux, f->dest, f->src, 0};
        } else {
            top--;
        }
    }

    free(stack);
}

int main() {
    int n = 3;
    hanoiIterative(n, 'A', 'C', 'B');
    return 0;
}

4、递归优化

通过优化递归调用，减少不必要的函数调用和变量复制，提高程序的执行效率。

#include <stdio.h> 
 
void hanoi_optimized(int n, char from, char to, char aux) { 
    static int depth = 0; 
    depth++; 
    if (n == 1) { 
        printf("Move disk 1 from %c to %c\n", from, to); 
        depth--; 
        return; 
    } 
    if (depth < 100) { // 限制递归深度，防止栈溢出 
        hanoi_optimized(n - 1, from, aux, to); 
        printf("Move disk %d from %c to %c\n", n, from, to); 
        hanoi_optimized(n - 1, aux, to, from); 
    } 
    depth--; 
} 
 
int main() { 
    int n = 3; // Number of disks 
    hanoi_optimized(n, 'A', 'C', 'B'); // A, B and C are names of rods 
    return 0; 
}