JavaScript实现汉诺塔算法:递归逻辑详解与代码示例
深入解析经典汉诺塔算法的递归与分治思想,提供规范可执行的JavaScript实现、3阶状态推导演进、递归树执行时序以及时间与空间复杂度全方位解析。
一、汉诺塔的游戏规则与物理约束
汉诺塔(Tower of Hanoi)源于古老的数学寓言。其物理模型由三根立柱以及若干个大小各异的圆盘组成。在游戏初始状态下,所有圆盘自底向上、按直径由大到小套在第一根柱子上,形成一座规整的宝塔。
算法的目标是将这座圆盘塔完整迁移至第三根柱子上,并严格遵守以下三条物理约束:
- 每次只能移动一个圆盘:必须从某根柱子的最顶端取下一块圆盘,平移并放置在另一根柱子的最顶端。
- 严禁以大压小:在移动的任何瞬间,任何柱子上的大圆盘都绝不能压在小圆盘的上方。
- 三根柱子角色明确:三根柱子分别扮演“源柱(Source)”、“辅助中转柱(Auxiliary)”与“目标柱(Target)”,但随着算法递进,柱子的身份会动态轮换。
二、核心心智模型:分治三步法
初学者在面对汉诺塔时,常常容易陷入“模拟具体每一步该把哪个盘子放到哪根柱子”的微观泥潭。当圆盘数量增加时,这种穷举思维会迅速超出人脑的工作记忆负荷。
递归解法的关键在于宏观归纳与分治抽象。假设我们要把 n 个圆盘从柱子 A 搬迁到柱子 C(借助柱子 B),我们不要去管前 n - 1 个圆盘具体如何腾挪,而是将它们视作一个整体的“子塔”,整个求解过程即可严格收敛为三大宏观步骤:
- 步骤一(子塔腾挪):将前 n - 1 个圆盘整体从源柱 A 移动到辅助柱 B,此时目标柱 C 充当临时过渡通道。
- 步骤二(底盘归位):此时源柱 A 上只剩下唯一且最大的第 n 号圆盘,目标柱 C 完全空置,直接将第 n 号圆盘从 A 移动到 C。
- 步骤三(子塔归宿):将已暂存在辅助柱 B 上的 n - 1 个圆盘整体移动到目标柱 C,此时源柱 A 充当临时过渡通道。
三、JavaScript 完整代码实现
基于上述三步推导,我们可以写出极度凝练的 JavaScript 递归函数。为了方便验证执行结果,我们在函数中接收一个数组参数,记录每一步的移动操作,并附带控制台执行演示。
/**
* 递归求解汉诺塔算法
* @param {number} n - 当前需要移动的圆盘数量
* @param {string} from - 源柱标识 (例如 'A')
* @param {string} to - 目标柱标识 (例如 'C')
* @param {string} aux - 辅助柱标识 (例如 'B')
* @param {Array} steps - 记录操作步骤的数组
* @returns {Array} 完整的移动步骤记录列表
*/
function solveHanoi(n, from, to, aux, steps = []) {
// 1. 基底条件:只有一个圆盘时,直接移动并返回
if (n === 1) {
steps.push({ step: steps.length + 1, disk: 1, from, to });
return steps;
}
// 2. 步骤一:将前 n-1 个盘子从 from 移到 aux,借助 to
solveHanoi(n - 1, from, aux, to, steps);
// 3. 步骤二:将第 n 个(最大)盘子从 from 移到 to
steps.push({ step: steps.length + 1, disk: n, from, to });
// 4. 步骤三:将 n-1 个盘子从 aux 移到 to,借助 from
solveHanoi(n - 1, aux, to, from, steps);
return steps;
}
// 执行示例:计算 3 阶汉诺塔的完整移动路径
const moves = solveHanoi(3, 'A', 'C', 'B');
// 格式化输出示例
console.log(`总共完成移动步数: ${moves.length}`);
moves.forEach(({ step, disk, from, to }) => {
console.log(`第 ${step} 步: 将 [圆盘 ${disk}] 从 ${from} 柱移动到 ${to} 柱`);
});
示例运行结果
在 Node.js 或浏览器开发者工具控制台中执行上述代码,将得到确定性的 7 步移动日志:
总共完成移动步数: 7
第 1 步: 将 [圆盘 1] 从 A 柱移动到 C 柱
第 2 步: 将 [圆盘 2] 从 A 柱移动到 B 柱
第 3 步: 将 [圆盘 1] 从 C 柱移动到 B 柱
第 4 步: 将 [圆盘 3] 从 A 柱移动到 C 柱
第 5 步: 将 [圆盘 1] 从 B 柱移动到 A 柱
第 6 步: 将 [圆盘 2] 从 B 柱移动到 C 柱
第 7 步: 将 [圆盘 1] 从 A 柱移动到 C 柱
四、3阶汉诺塔的 7 步状态演进流转
为了让初学者建立真实的物理映射,我们以 n = 3 为例,将上述代码生成的 7 步移动过程,映射为三根柱子上圆盘位置的连续流转图。
观察上图可以清晰地看到分治法的节奏点:
- 第 1 至 3 步:对应第一项子任务
solveHanoi(2, 'A', 'B', 'C'),目的是把圆盘 1 与圆盘 2 安全转移到 B 柱上。 - 第 4 步:关键节点!最大圆盘 3 从 A 移到 C,完成了它一生中唯一的一次移动。
- 第 5 至 7 步:对应第二项子任务
solveHanoi(2, 'B', 'C', 'A'),把 B 柱上的圆盘 1 与圆盘 2 复原叠放在 C 柱的圆盘 3 上。
五、递归调用树与执行栈时序
JavaScript 引擎在执行递归函数时,依靠“执行上下文栈(Call Stack)”管理函数的进出。每一次函数调用都会压入一个栈帧,记录当前的局部变量与参数;触底返回后,栈帧弹出,上一层函数继续执行后续代码。
汉诺塔的递归结构是一棵典型的二叉递归树。对于 solveHanoi(3),代码自顶向下深入,按照“深度优先遍历(DFS)”的顺序依次执行左子树、中间叶子输出、右子树。
六、常见认知误区与深度辨析
误区一:参数名称固定对应实际柱子
很多初学者误以为 from 永远代表 A 柱,to 永远代表 C 柱。
修正:形参是“角色名称”,实参才是“物理柱子”。在子调用 solveHanoi(n-1, aux, to, from) 中,B 柱实际上作为 from 传入,而 A 柱则变成了 aux。
误区二:脑中需时刻预演多步盘位
尝试在写代码时推演盘子每一步会掉到哪根柱子,导致思维混乱。
修正:递归是“面向结果的契约”。只要相信 solveHanoi(n-1) 能正确把子塔移到辅助柱,就能直接写出清晰优雅的顶层步骤。
七、算法复杂度与适用边界
汉诺塔问题的时间开销与空间开销呈现截然不同的两种数学特性:
1. 时间复杂度:O(2ⁿ)
设移动 n 个盘子需要的步数为 T(n)。根据递归公式:
T(1) = 1
T(n) = 2 · T(n-1) + 1
展开可得:T(n) = 2ⁿ - 1。这意味着每多增加一个圆盘,算法所需的移动操作次数就会直接翻倍加一。这属于典型的指数级时间复杂度 O(2ⁿ)。
2. 空间复杂度:O(n)
尽管总移动步数是指数级的,但 JavaScript 引擎所消耗的内存栈空间却仅仅取决于递归树的最大高度。由于每一次递归调用都将 n 递减 1,调用栈在任意时刻的最大深度恰好为 n。因此,汉诺塔算法的辅助空间复杂度为严格的线性复杂度 O(n)。
| 圆盘数量 n | 理论移动步数 (2ⁿ - 1) | 最大调用栈深度 | 实际工程评估 |
|---|---|---|---|
| 3 个 | 7 步 | 3 帧 | 毫秒级瞬时完成 |
| 5 个 | 31 步 | 5 帧 | 毫秒级瞬时完成 |
| 10 个 | 1,023 步 | 10 帧 | 极快,几乎无感知 |
| 20 个 | 1,048,575 步 | 20 帧 | 约需几秒输出(受限于IO) |
| 64 个 | 18,446,744,073,709,551,615 步 | 64 帧 | 若每秒移动一次,需超 5800 亿年 |
八、总结
汉诺塔算法是计算机科学中最具代表性的递归范例之一。通过将复杂的组合推演解构成“子塔中转、底盘就位、子塔归位”的三步分治,我们以仅 10 余行极其精简的 JavaScript 代码,解决了规模庞大的指数级任务。
在实际编程中,掌握汉诺塔不仅有助于深刻理解树的深度优先遍历、函数执行上下文栈与分治法,更能培养在面对复杂工程问题时“信任抽象、逐层解耦”的高阶架构思维。
JavaScript Map集合怎么取值?get方法与遍历技巧
2026-11-17 22:43:04
JS回调函数中为何常使用函数表达式而非声明
2026-11-17 19:13:24
JS数组怎么在末尾添加元素?push用法与返回值说明
2026-11-17 19:11:17
JS表格排序怎么处理中文拼音及日期格式
2026-11-17 16:31:58
JS怎么从数组中随机选取一个或多个不重复元素
2026-11-17 15:48:43








