【C语言】函数递归：汉诺塔问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C语言】函数递归：汉诺塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

汉诺塔问题是一道经典的计算机科学中的递归算法题，通过解决汉诺塔问题以更好的理解递归。

函数递归

函数递归：函数自己调用自己。

函数递归的两个必要条件：
1.函数自身的调用要有限制条件，如果没有限制条件，就会无限的自己调用自己而导致栈溢出（stack overflow）(关于栈溢出的问题我会再出一篇文章详细分析底层)。
2.函数每一次调用自己时，要逐渐接近限制条件。

函数递归的本质：大事化小。把一个大问题分解成若干个小问题。

什么是汉诺塔问题？

问题的描述如下：

有三根柱子，标记为A、B、C，A柱子上有n个大小不同的盘子，盘子从下到上按照大小递增排列。现在需要将A柱子上的所有盘子移动到C柱子上，移动过程中可以借助B柱子，但是每次只能移动一个盘子，并且大盘子不能放在小盘子上面。

起始状态：

目标状态：

移动过程中的违规状态（大盘子在小盘子上面）：

题目

请用C语言实现以下功能：输入在A柱子上的盘子数，输出所有盘子从A柱子移动到C柱子的整个过程。

解题思路

只要把解题思路搞明白了，无论用什么编程语言，都只是一种思路的不同表示形式而已。

1. 移两个盘子

先从最简单的移两个盘子开始分析：
利用递归函数调用解决移动10个盘子的汉诺塔问题,c语言,算法,笔记
两个盘子从A柱移到C柱的过程：

小盘子先从A柱移到B柱
然后大盘子从A柱移到C柱
最后小盘子从B柱移到C柱。

过程简写如下：

A–>B
A–>C
B–>C

要想让A柱最底下最大的盘子移到C柱上，只有上面的小盘子移到B柱时，大盘子才能从A柱移到C柱。

2. 移n个盘子

知道怎么移两个盘子之后再看移n个盘子：
利用递归函数调用解决移动10个盘子的汉诺塔问题,c语言,算法,笔记
移两个盘子和移n个盘子的相同之处：

无论A柱有多少个盘子，想要让A柱最底下最大的盘子移到C柱上，只有这大盘子上面所有的小盘子都移到B柱时，最下面的大盘子才能从A柱移到C柱。
所以我们可以先把上面的n-1个盘子看成一个整体，把这个整体从A柱移到B柱，再把最下面的盘子从A柱移到C柱。
步骤1.把前n-1个盘子组成的整体从A柱移到B柱

步骤2.再把最下面的盘子从A柱移到C柱。

步骤3.把前n-1个盘子组成的整体从B柱移到C柱

在不考虑怎么移前n-1个盘子的情况下，上面的这三个步骤和移两个盘子的步骤简直一模一样！

那具体怎么移动上面的n-1个盘子呢？

以步骤3中为例：把前n-1个盘子组成的整体从B柱移到C柱的过程中，这个整体又可以划分为前n-2个盘子组成的整体和第n-1个盘子

想要把第n-1个盘子从B柱移到C柱，得先把上面的前n-2个盘子看成一个整体，这个整体从B柱移到A柱。

发现了吗？我已经正在把一个大问题拆分成若干个小问题了：
刚开始的大问题是在A柱上面的n个盘子从A柱移到C柱，在上面的步骤1 和步骤3 中，又可以细分成一些小问题：把n-1个盘子从A柱和B柱，把n-1个盘子从B柱和C柱这些。当然，在移动n-1个盘子的过程中会出现更小的问题。这些无数的小问题们直到遇见步骤2 的时候，也就是只有一个盘子的时候，不再需要再划分成更小的问题解决，直接移动这1个盘子即可。可能这个时候思路还比较乱，接下来我会在下面一节的抽象中展现完整的思路。

3.抽象

利用递归函数调用解决移动10个盘子的汉诺塔问题,c语言,算法,笔记
这里可能会有几个疑问：

每一次从一个柱子移到另一个柱子中，这两个柱子的位置不是固定的，怎么处理这些柱子的对应关系？
什么时候不会再划分出两个新的函数，也就是说限制条件是什么？

第一个问题回答：我们不能全部知道各种情况什么柱要移到什么柱，但是他们有共同的特点：都是从起始的柱子移到目的地柱子，总有一个柱子是第三者当工具。我们可以称起始的柱子为起始柱，称目的地柱子为目标柱，称第三者为工具柱。

A柱，B柱，C柱是固定的，但是他们每次充当的角色可以是不同的 (起始柱，目标柱，工具柱)。

第二个问题回答：当n减到1时，也就是只有一个盘子时，按照上面的3个步骤走一遍，发现只需走第二个步骤，因为第一个和第三个步骤是0个盘子从起始柱移到目标柱，没有盘子了就肯定不要执行啦。

所以限制条件是n>0。

综上所述：
解决汉诺塔问题的函数需要用到4个变量：

盘子的个数n
起始柱
目标柱
工具柱

有了步骤,参数还有限制条件，代码的实现就轻松很多了。

代码实现

#include<stdio.h>

//        盘子个数  起始柱  目标柱  工具柱
void hanoi(int n, char A, char C, char B)
{
	if (n > 0)//限制条件
	{
		//第一步，把A柱上面的n-1个盘子移到B柱。此时A柱为起始柱，B柱为目标柱，C柱为工具柱
		hanoi(n - 1, A, B ,C);

		//第二步，直接输出A柱最底下最大的盘子移到C柱的过程。此时A柱为起始柱，C柱为目标柱
		printf("%c-->%c\n", A, C);

		//第三步，把B柱上面的n-1个盘子移到C柱。此时B柱为起始柱，C柱为目标柱，A柱为工具柱
		hanoi(n - 1, B, C, A);
	}
}


int main()
{
	int n = 0;
	printf("请输入在A柱上的盘子的个数:>");
	scanf("%d", &n);
	char A = 'A';
	char B = 'B';
	char C = 'C';
	hanoi(n,A,C,B);
	return 0;
}