汉诺塔
进阶汉诺塔是理解递归拆解与状态转移的教科书例子。
// 算法讲解
汉诺塔
演示将所有盘子从 A 柱移到 C 柱的递归过程。
待机
速度 中
待机 ⌨1void hanoi(int n, char from, char buffer, char to) {
2 if (n == 0) return;
3 hanoi(n - 1, from, to, buffer);
4 cout << from << " -> " << to << "\n";
5 hanoi(n - 1, buffer, from, to);
6}
复杂度分析
时间 O(2^n)
空间 O(n)
最优 O(1)
最坏 O(2^n)
算法讲解
把 n 个盘子从 A 搬到 C，看似复杂，但递归视角下可以拆成"先搬上面 n-1 个、再搬最大盘、再搬回 n-1 个"。
这道题最适合训练"函数相信子问题会被正确解决"的递归思维，而不是自己在脑中硬推所有步骤。
它还天然呈现出递归树和调用栈的增长方式，因此非常适合做可视化内容。
总步数是 2^n - 1，也提醒我们递归优雅不代表复杂度一定低。