C语言运用函数的递归实现汉诺塔

C语言运用递归实现汉诺塔的攻略

理解汉诺塔问题

汉诺塔问题是经典的递归运用问题。可以转化为：将n个盘从A经由B移动到C，其中每次只能移动一个盘，且在移动过程中不能将大盘放在小盘上面。如下图所示：

     |           |           |
    ===          |           |
   =====         |           |
  =======        |           |
 =======         |           |
---------------- A --------- B --------- C

理解递归思想

递归是一种函数自己调用自己的算法。实现递归的方法是：找到一个最基本、最小的问题解，利用它来结束函数的递归。而且每次递归调用规模相比初始时都有所减少。因此，我们通常使用递归求解复杂问题，可以减少程序代码的复杂性。

使用递归求解汉诺塔问题

递归求解汉诺塔问题的思想是：把n个盘子从A柱移到C柱，可以分为三个步骤：

• 将前n-1个盘子从A移动到B，利用C作为中转站；
• 将第n个盘子从A移到C；
• 将B柱上的n-1个盘子移动到C，利用A作为中转站。

然后我们发现，第一步和第三步可以直接套用递归函数来实现，实现代码如下：

void hanoi(int n, char a, char b, char c) {
    if (n == 1)
        printf("%c -> %c\n", a, c);
    else {
        hanoi(n-1, a, c, b);    // Step 1
        printf("%c -> %c\n", a, c);    // Step 2
        hanoi(n-1, b, a, c);    // Step 3
    }
}

其中，n表示盘子的数量，a、b、c分别表示三个柱子。当n等于1时，直接将一个盘子从a移到c；否则，将前n-1个盘牌从a移到b（利用c作为中转站），再将第n个盘子从a移到c，最后将b上的n-1个盘子移动到c（利用a作为中转站）。这三个步骤经过递归自然就会实现。

示例

1. 当有三个盘子时，运行下面的代码：

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

其输出结果如下：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

1. 当有四个盘子时，运行下面的代码：

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

其输出结果如下：

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
A -> C
B -> C
B -> A
C -> A
B -> C
A -> B
A -> C
B -> C

总结

递归求解汉诺塔问题是经典的递归运用问题。实现递归的方法是：找到一个最基本、最小的问题解，利用它来结束函数的递归。要注意每次递归调用规模相比初始时都有所减少，才能够达到问题的求解。