汉诺塔 | Java 递归实现

📚 目录

• 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递归实现汉诺塔

publicclasstest1{//打印路线publicstaticvoidmove(charstr,chardest){System.out.print(str+"->"+dest+" ");}//n:盘子个数 pos1：柱子A pos2:柱子B pos3:柱子Cpublicstaticvoidhaoni(intn,charpos1,charpos2,charpos3){if(n==1){//pos1->pos3move(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);}publicstaticvoidmain(String[]args){haoni(3,'A','B','C');}}

汉诺塔中有64个盘子，如果每秒移动一个盘子，且移动是正确的那他需要挪动2^64 - 1秒，大概是5800多年，就算是计算机也需要跑很久很久。
找到递归的地推公式和结束条件那么递归的题目就很好做了。