📚 目录
- 1. 什么是汉诺塔？
- 2.汉诺塔解决前分析
- 3.Java递归实现汉诺塔
前言： 汉诺塔是学习递归的经典例题。本文使用 Java 递归实现汉诺塔问题，详细讲解思路与代码，帮助初学者理解递归思想。
1. 什么是汉诺塔？
简单来说就是有三根柱子，有根柱子上面放着一串的盘子，我们需要借助三根中的一根柱子把盘子移动到另外一个柱子上，需要按照大到小的顺序进行放置。（小盘上面不能是大盘）
🔙 返回目录
2. 汉诺塔解决前分析
在外面了解到了什么是汉诺塔之后，就要开始进行我们的分析了。 
假设我们的柱子是A、B、C三根柱子 当我们只有一个盘子的时候，直接就是A -> C盘上面。
当我们有两个盘子的时候： 
我们就需要将小的盘子先放到B上面然后将大的盘子放到C上面，最后把B上的盘子放到C上面。 
当我们A柱子上面有3个盘子的时候： 
我们先需要把上面两个小的盘子借助C把把盘子移动到B上 
A->C,A->B,C->B,A->C,B->A,B->C,A->C这就是我们挪动的顺序。
分析： 
如果使用递归该怎么做呢？ 我们需要找我们的递推公式：步数：2^n – 1 结束条件：也就是A盘只有一个盘子的时候直接挪动到C盘上 前置条件：先把n-1个盘子借助C放到B上。把剩下的一个盘子从A挪动到C上。 
最后在把n-1个盘子借助A放到C上。 
当我们在使用递归的时候注意：不要使用纵向展开，我们的脑容量是有限的，展开不完；使用横向的方式有助于我们用递归解决问题。
🔙 返回目录
3. Java递归实现汉诺塔
public class test1 {
//打印路线
public static void move (char str,char dest) {
System.out.print(str+"->"+dest +" " );
}
//n:盘子个数 pos1：柱子A pos2:柱子B pos3:柱子C
public static void haoni(int n ,char pos1,char pos2,char pos3) {
if(n==1) {
//pos1->pos3
move(pos1,pos3);
return;
}
//将n-1个盘子借助柱子C移动到B上
haoni(n–1,pos1,pos3,pos2);
move(pos1,pos3);
//将剩下的n-1个盘子借助柱子A移动到C上
haoni(n–1,pos2,pos1,pos3);
}
public static void main(String[] args) {
haoni(3,'A','B','C');
}
}
汉诺塔中有64个盘子，如果每秒移动一个盘子，且移动是正确的那他需要挪动2^64 – 1秒，大概是5800多年，就算是计算机也需要跑很久很久。 找到递归的地推公式和结束条件那么递归的题目就很好做了。
🔙 返回目录
