【高级技巧】汉诺塔：递归分解的移动规划

底层原理

三根柱子 n 个盘子从 A 全部移到 C、大盘永不在小盘上：递归分解是唯一优雅解——先把上面 n-1 个从 A 借 B 移到 C？不，标准分解是先把 n-1 个从 A 借 C 移到 B，再把最大盘从 A 移到 C（1 步），收尾把 n-1 个从 B 借 A 移到 C。移动次数恰为 2^n - 1：n=64 时约 1844 亿亿步，这是世界末日传说的数学来源。递归停止条件只有一个：1 个盘子直接移。

高级封装

递归分解移动。示例代码如下：

local function hanoi(n, from, via, to, moves)
    if n == 1 then
        moves[#moves + 1] = from .. "->" .. to
        return
    end
    hanoi(n - 1, from, to, via, moves)
    moves[#moves + 1] = from .. "->" .. to
    hanoi(n - 1, to, from, to, moves)
end
local moves = {}
hanoi(3, "A", "B", "C", moves)
print(#moves, moves[1])

3 个盘子 7 步——分解结构与步数公式 2^n - 1 严丝合缝。
关卡脚本接线。示例代码如下：

local steps = {}
hanoi(5, "A", "B", "C", steps)
print(#steps)

5 盘 31 步——祖玛阁机关谜题类玩法可按 n 生成标准答案序列，玩家的步数与标准比对评分。

性能对比

3 盘 7 步、10 盘 1023 步、20 盘约 105 万步——步数随 n 指数增长，序列模拟的上限约 25 盘（3000 万步、内存约 1.2GB）。递归只有 n 层极浅（25 层远低于栈限），真正的成本在移动序列的存储，不在递归本身。

适用边界

三个不适用场景：一是 n 超过 25 的纯模拟——步数爆炸序列不可存，只应输出步数公式；二是变体规则（限制某两柱间不可移）需要重新推导递归结构，不能照搬标准式；三是序列用于实时玩法时，边玩边生成下一步比一次性生成全部序列更省内存。