doocs/leetcode 汉诺塔问题（面试题 08.06）题解精讲：从递归到显式栈的两种实现-平芜编程栈

示例工程
教程

【免费下载链接】leetcode

🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

汉诺塔（Towers of Hanoi）是递归思维最经典的载体，也是《程序员面试金典（第 6 版）》第 08.06 题的核心考点。本篇基于 lcci/08.06.Hanota/README_EN.md 展开，结合 doocs/leetcode 仓库中 Python、Java、C++、Go、TypeScript、Swift 多语言源码，完整剖析问题约束、最优移动序列的数学性质，以及「递归」与「迭代（显式栈）」两种解法的设计与复杂度。读完你将掌握汉诺塔问题的标准递归模板、如何用任务栈消除递归深度限制，以及2^n - 1最短步数的证明路径。

问题概述与约束

在经典汉诺塔问题中，有 3 根柱子（A、B、C）和 N 个大小不同的穿孔圆盘，圆盘可以滑入任意一根柱子。初始时，所有盘子自上而下按升序（小盘在上、大盘在下）套在第一根柱子 A 上。移动时必须遵守三条限制：

每次只能移动一个盘子；
盘子只能从柱子顶端滑出，移到下一根柱子；
盘子只能叠在比它大的盘子上（大盘不能压小盘）。

题目要求用栈（即把每根柱子视为一个栈）将所有盘子从第一根柱子 A 移到最后一根柱子 C，并且原地修改栈（不返回新数组，直接操作传入的 A、B、C 三个列表/数组）。

示例

示例 1

输入：A = [2, 1, 0]，B = []，C = [] 输出：C = [2, 1, 0]

示例 2

输入：A = [1, 0]，B = []，C = [] 输出：C = [1, 0]

注意列表下标 0 代表栈顶（即最小的盘子在最上面，位于数组尾部）。输入输出以数组形式表达：[2, 1, 0]表示从底到顶依次为 2、1、0。

提示：A.length <= 14，即盘子数目不超过 14 个。题目难度为「简单」，在 lcci/README.md 总表中归类标签为递归。

核心思路：为什么最优移动序列是唯一的

直接模拟「每一步的合法移动」来做搜索是不可行的：三柱汉诺塔在任意状态下，合法移动的状态数为指数级。原文档的分析指出，若用穷举搜索，状态数会达到3^n，随 n 迅速爆炸。真正的高效解法依赖一个关键洞察：

要移动 n 个盘子从 A 到 C，必须先把最大的第 n 个盘子暴露出来，而它只能移动到空的目标柱 C 上。因此移动过程被唯一地分解为三步：

先把上面n - 1个盘子从 A 借助 C 移到辅助柱 B；
再把最大的第 n 个盘子从 A 直接移到 C；
最后把n - 1个盘子从 B 借助 A 移到 C。

这个「把大问题拆成规模为 n-1 的两个子问题」的过程可以不断递归下去，直到n = 1时只剩一次直接移动。由此可以严格推导出两个数学结论：

最短步数：设T(n)为移动 n 个盘子的最少步数，则T(1) = 1，T(n) = 2·T(n-1) + 1，解得T(n) = 2^n - 1。原文档中的「总步数2^n - 1，与经典结论一致」即源于此。
最优策略唯一：每一步都必须遵循「先移 n-1、再移底盘、再移 n-1」的次序，没有更优的替代路径。

方法一：递归实现 dfs(n, a, b, c)

算法设计

设计递归函数dfs(n, a, b, c)，语义为：将 n 个盘子从柱子 a 移动到柱子 c，b 为辅助柱子。递归体严格对应上述三步：

若n == 1：直接将 a 的栈顶盘子弹出并压入 c，即一次pop/append；
否则：
1. dfs(n - 1, a, c, b)：把 n-1 个盘子从 a 借助 c 移到 b；
2. 把第 n 个（最大的）盘子从 a 弹出压入 c；
3. dfs(n - 1, b, a, c)：把 n-1 个盘子从 b 借助 a 移到 c。

外层入口调用dfs(len(A), A, B, C)。因为题目要求原地修改栈，所有语言版本都直接操作传入的数组/列表，不额外分配结果容器。

复杂度分析

时间复杂度O(2^n)：每层递归产生两个规模为 n-1 的子问题，递归树总节点数为2^(n+1) - 1，与最短步数2^n - 1同阶；
空间复杂度O(n)：递归调用栈的最大深度为 n（不含输入数据本身的存储）。

各语言实现

以下实现与仓库源码 lcci/08.06.Hanota/Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift 完全一致。

Python3

class Solution: def hanota(self, A: List[int], B: List[int], C: List[int]) -> None: def dfs(n, a, b, c): if n == 1: c.append(a.pop()) return dfs(n - 1, a, c, b) c.append(a.pop()) dfs(n - 1, b, a, c) dfs(len(A), A, B, C)

Java

class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { dfs(A.size(), A, B, C); } private void dfs(int n, List<Integer> a, List<Integer> b, List<Integer> c) { if (n == 1) { c.add(a.remove(a.size() - 1)); return; } dfs(n - 1, a, c, b); c.add(a.remove(a.size() - 1)); dfs(n - 1, b, a, c); } }

C++

class Solution { public: void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { auto dfs = & { if (n == 1) { c.push_back(a.back()); a.pop_back(); return; } dfs(n - 1, a, c, b); c.push_back(a.back()); a.pop_back(); dfs(n - 1, b, a, c); }; dfs(A.size(), A, B, C); } };

func hanota(A []int, B []int, C []int) []int { var dfs func(n int, a, b, c *[]int) dfs = func(n int, a, b, c *[]int) { if n == 1 { *c = append(*c, (*a)[len(*a)-1]) *a = (*a)[:len(*a)-1] return } dfs(n-1, a, c, b) *c = append(*c, (*a)[len(*a)-1]) *a = (*a)[:len(*a)-1] dfs(n-1, b, a, c) } dfs(len(A), &A, &B, &C) return C }

注意 Go 版本没有原地修改的约束，因此签名返回[]int（最终返回 C），并且为了让子调用能修改切片本身，参数使用*[]int指针。

TypeScript

/** Do not return anything, modify C in-place instead. */ function hanota(A: number[], B: number[], C: number[]): void { const dfs = (n: number, a: number[], b: number[], c: number[]) => { if (n === 1) { c.push(a.pop()!); return; } dfs(n - 1, a, c, b); c.push(a.pop()!); dfs(n - 1, b, a, c); }; dfs(A.length, A, B, C); }

Swift

class Solution { func hanota(_ A: inout [Int], _ B: inout [Int], _ C: inout [Int]) { dfs(n: A.count, a: &A, b: &B, c: &C) } private func dfs(n: Int, a: inout [Int], b: inout [Int], c: inout [Int]) { if n == 1 { c.append(a.removeLast()) return } dfs(n: n - 1, a: &a, b: &c, c: &b) c.append(a.removeLast()) dfs(n: n - 1, a: &b, b: &a, c: &c) } }

Swift 版本同样通过inout参数原地修改三个数组，入口在 Solution.swift。

正确性验证：以示例 1 为例

对A = [2, 1, 0]（栈顶为 0），递归执行轨迹为：

dfs(3, A, B, C)→dfs(2, A, C, B)→dfs(1, A, B, C)：将 0 从 A 移到 C；
回到dfs(2, ...)，将 1 从 A 移到 B；
dfs(1, C, A, B)：将 0 从 C 移到 B（此时 B = [1, 0]）；
回到dfs(3, ...)，将 2 从 A 移到 C（此时 C = [2]）；
dfs(2, B, A, C)→dfs(1, B, C, A)：将 0 从 B 移到 A；
将 1 从 B 移到 C（C = [2, 1]）；
dfs(1, A, B, C)：将 0 从 A 移到 C，最终C = [2, 1, 0]。✓

整趟共移动 7 次，恰好等于2^3 - 1，与理论最短步数一致。

方法二：迭代实现（显式任务栈）

为什么需要迭代版本

递归版本已经能给出最短移动序列，但某些评测环境会限制递归调用深度。本题A.length <= 14，递归深度最多 14 层通常没有问题；不过一旦推广到盘子更多的场景，或迁移到递归深度受限的运行时，显式栈的迭代写法就更稳妥。原文档的思考备注也明确指出了这一动机：「Recursion already emits the shortest sequence, but some judges limit call depth.」

算法设计

用显式栈模拟递归过程。定义任务结构体Task，其中n表示本次要移动的盘子数目，a、b、c表示三根柱子（按「源、辅助、目标」的语义传参）。

将初始任务Task(len(A), A, B, C)压入栈；

循环取出栈顶任务处理，直到栈为空：

若n == 1：直接执行移动——将 a 的栈顶弹出压入 c；

否则，逆序压入三个子任务，使弹出顺序恰好等于正确执行顺序：

压入顺序（先压的在后出）	弹出即执行的子任务	语义
第 1 个压入	`(n-1, b, a, c)`	将 n-1 个盘子从 b 借助 a 移动到 c
第 2 个压入	`(1, a, b, c)`	将第 n 个盘子从 a 移动到 c
第 3 个压入	`(n-1, a, c, b)`	将 n-1 个盘子从 a 借助 c 移动到 b

由于栈是后进先出（LIFO），先压入的任务后弹出。上面三个子任务依次压入后，弹出的次序正好是：先移 n-1（a→b）、再移底盘（a→c）、再移 n-1（b→c），与递归版本的执行顺序完全一致。这也是原文档强调的「按『后进先出』压入三个子任务，使弹出次序仍是先移 n-1、再移底盘、再移 n-1」的落地方式。

复杂度分析

时间复杂度O(2^n)：任务总数与递归树节点数同阶，仍为指数级；
空间复杂度O(n)：栈中同时存在的最大任务数为 O(n)（沿一条递归路径展开的任务链）。

各语言实现

以下实现与仓库源码 lcci/08.06.Hanota/Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts 完全一致。

Python3（元组直接充当 Task）

class Solution: def hanota(self, A: List[int], B: List[int], C: List[int]) -> None: stk = [(len(A), A, B, C)] while stk: n, a, b, c = stk.pop() if n == 1: c.append(a.pop()) else: stk.append((n - 1, b, a, c)) stk.append((1, a, b, c)) stk.append((n - 1, a, c, b))

Java（用内部类 Task 封装）

class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { Deque<Task> stk = new ArrayDeque<>(); stk.push(new Task(A.size(), A, B, C)); while (stk.size() > 0) { Task task = stk.pop(); int n = task.n; List<Integer> a = task.a; List<Integer> b = task.b; List<Integer> c = task.c; if (n == 1) { c.add(a.remove(a.size() - 1)); } else { stk.push(new Task(n - 1, b, a, c)); stk.push(new Task(1, a, b, c)); stk.push(new Task(n - 1, a, c, b)); } } } } class Task { int n; List<Integer> a; List<Integer> b; List<Integer> c; public Task(int n, List<Integer> a, List<Integer> b, List<Integer> c) { this.n = n; this.a = a; this.b = b; this.c = c; } }

C++（Task 中以指针引用原向量，实现原地修改）

struct Task { int n; vector<int>* a; vector<int>* b; vector<int>* c; }; class Solution { public: void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { stack<Task> stk; stk.push({(int) A.size(), &A, &B, &C}); while (!stk.empty()) { Task task = stk.top(); stk.pop(); if (task.n == 1) { task.c->push_back(task.a->back()); task.a->pop_back(); } else { stk.push({task.n - 1, task.b, task.a, task.c}); stk.push({1, task.a, task.b, task.c}); stk.push({task.n - 1, task.a, task.c, task.b}); } } } };

Go（切片指针传递）

func hanota(A []int, B []int, C []int) []int { stk := []Task{{len(A), &A, &B, &C}} for len(stk) > 0 { task := stk[len(stk)-1] stk = stk[:len(stk)-1] if task.n == 1 { *task.c = append(*task.c, (*task.a)[len(*task.a)-1]) *task.a = (*task.a)[:len(*task.a)-1] } else { stk = append(stk, Task{task.n - 1, task.b, task.a, task.c}) stk = append(stk, Task{1, task.a, task.b, task.c}) stk = append(stk, Task{task.n - 1, task.a, task.c, task.b}) } } return C } type Task struct { n int a, b, c *[]int }

TypeScript

/** Do not return anything, modify C in-place instead. */ function hanota(A: number[], B: number[], C: number[]): void { const stk: any[] = [[A.length, A, B, C]]; while (stk.length) { const [n, a, b, c] = stk.pop()!; if (n === 1) { c.push(a.pop()); } else { stk.push([n - 1, b, a, c]); stk.push([1, a, b, c]); stk.push([n - 1, a, c, b]); } } }

TypeScript 版本用数组直接存储[n, a, b, c]四元组，免去了单独定义 Task 类型的样板代码。

两种解法对比

维度	方法一：递归	方法二：迭代（显式栈）
核心机制	函数调用栈隐式保存任务	自建`Task`栈显式保存任务
时间复杂度	`O(2^n)`	`O(2^n)`
空间复杂度	`O(n)`（递归调用深度）	`O(n)`（栈内任务数）
代码直观度	高，与数学推导一一对应	中，需理解「逆序压入、LIFO 弹出」
递归深度风险	受调用栈深度限制	无（推荐用于盘子数大的场景）
原地修改	是（各语言直接操作传入数组）	是（同左）

两种方法产出的移动序列完全相同，都满足最短步数2^n - 1，在本题A.length <= 14的规模下性能差异可忽略。选型建议：面试讲解优先用递归版本（逻辑清晰、易于证明正确性）；若追问工程化场景（如盘子数上千、递归深度受限的嵌入式环境），再补充迭代版本并解释任务栈的压入次序。

仓库源码佐证

本题在 doocs/leetcode 仓库lcci/08.06.Hanota/目录下的完整文件如下，可直接对照阅读：

题解文档：中文版、英文版，英文版即本文的原始依据；
递归解法：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift；
迭代解法：Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts。

需要说明的是，仓库中 Go 版本的两种解法均以func hanota(...) []int形式返回最终结果，与其它语言「原地修改 C、无返回值」的签名略有差异，这属于 Go 切片传参的惯用写法（切片本身是引用类型，但append可能触发扩容，故源码采用*[]int指针保证修改生效）。其余语言均严格遵循题目「原地修改」的要求。

小结

汉诺塔问题看似古老，却是面试中考察递归建模、分治思想与栈理解的经典题目：

建模是关键：dfs(n, a, b, c)的三段式分解（n-1 移辅助、底盘移目标、n-1 移目标）直接来自「大盘必须最后落位」这一约束，推导出的2^n - 1最短步数可作为验证实现正确性的天然基准；
递归与迭代殊途同归：显式任务栈按「逆序压入」即可精确复现递归执行次序，理解这一转换对掌握「递归转迭代」的通用技巧很有帮助；
多语言对照：本仓库提供了 6 种主流语言的实现，覆盖原地修改、指针传参、inout 参数等语言特性差异，是学习同一算法在不同语言中落地写法的优质素材。

如果需要进一步练习，可回到 lcci/README.md 总表，继续阅读同为「递归」标签的 08.05 递归乘法、16.11 跳水板等题目，巩固递归建模能力。