递归 · 汉诺塔

递归 · 汉诺塔（1521 真题同款）

有三根柱子 A、B、C，A 上从大到小叠着 n 个盘子。把它们全部从 A 移到 C，规则：每次只能搬一个盘子，且任何时候大盘不能压在小盘上。请用递归输出每一步搬法。

递归的精髓——把「搬 n 个」拆成两个「搬 n−1 个」的子问题：

1. 先把上面 n-1 个从 from 借助 to 挪到 via；
2. 把最底下最大的那个从 from 直接搬到 to（打印这一步）；
3. 再把那 n-1 个从 via 借助 from 挪到 to。

基准情形：n == 0 时什么都不用搬（直接返回）。请补全 hanoi。

易错点：① 漏写基准 n == 0 → 无限递归、栈溢出。② 两个递归调用的「借助柱」要传对——第一步借 to、第三步借 from，搞反会违反规则。③ 打印那一步要夹在两个递归调用中间。

输入

• 一行：整数 n（0 ≤ n ≤ 12），盘子数。

输出

• 每行一步，格式 X -> Y（从 X 柱搬到 Y 柱）。n 个盘子恰好 2^n − 1 步；n = 0 时无输出。

示例：输入 2 → 输出三行 A -> B / A -> C / B -> C。