C++ 递归实战：汉诺塔问题的思路与实现

汉诺塔问题解析

核心思路

汉诺塔是递归教学中的经典案例。理解它的关键在于拆解问题规模，将复杂的大问题转化为简单的子问题。

假设我们有三根柱子 A、B、C，初始时 A 柱上有 n 个盘子，从小到大叠放。目标是将所有盘子从 A 移动到 C，过程中大盘子不能压在小盘子上面。

我们可以从最简单的情况开始推导：

• n = 1：直接将 A 顶部的盘子移到 C。
• n = 2：借助 B 柱。先将小盘（1 号）移到 B，再将大盘（2 号）移到 C，最后将小盘从 B 移到 C。
• n > 2：策略依然遵循同样的逻辑。我们将 A 上方的 n-1 个盘子视为一个整体，先移到辅助柱 B；接着将最大的第 n 个盘子直接移到目标柱 C；最后将 B 上的 n-1 个盘子再移到 C。

这种'分而治之'的思想正是递归的核心：规模为 n 的问题依赖于规模为 n-1 的解法。

算法流程

设计一个递归函数 dfs，参数包括三个柱子的引用和当前需要移动的盘子数量 n。

1. 终止条件：当 n=1 时，直接将源柱顶部的盘子弹出并压入目标柱。
2. 递归步骤：
   • 第一步：将 A 柱上的 n-1 个盘子通过 C 柱暂存，移动到 B 柱。
   • 第二步：将 A 柱上剩余的最大盘子移动到 C 柱。
   • 第三步：将 B 柱上的 n-1 个盘子通过 A 柱暂存，移动到 C 柱。

注意在递归调用中，辅助柱和目标柱的角色会互换，这是初学者容易混淆的地方，务必理清参数顺序。

代码实现

下面是基于 C++ STL vector 的实现，利用栈的特性模拟柱子操作。

class Solution {
public:
    // 深度优先搜索，负责具体的移动逻辑
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n) {
        if (n == 1) {
            // 只有一个盘子，直接移动
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        
        // 将 A 上 n-1 个盘子移到 B（此时 C 作为辅助）
        dfs(A, C, B, n - 1);
        
        // 将 A 上最大的盘子移到 C
        C.push_back(A.back());
        A.pop_back();
        
        
        (B, A, C, n - );
    }

    {
         n = A.();
        (A, B, C, n);
    }
};