C++ 递归算法实战：汉诺塔问题详解

问题背景

汉诺塔是递归算法中最经典的入门题目之一。给定三根柱子 A、B、C 和 n 个大小不同的圆盘，初始时所有圆盘按大小顺序叠放在 A 柱上。目标是将所有圆盘移动到 C 柱，过程中必须遵守大盘不能压在小盘上的规则，且每次只能移动一个圆盘。

递归思路

解决这个问题的关键在于'分治'思想。当 n=1 时，直接将 A 移到 C 即可。当 n>1 时，我们可以将其拆解为三个步骤：

1. 将 A 柱上方的 n-1 个盘子借助 C 柱移动到 B 柱；
2. 将 A 柱剩余的最大盘子直接移动到 C 柱；
3. 将 B 柱上的 n-1 个盘子借助 A 柱移动到 C 柱。

这样，规模为 n 的问题就转化为了两个规模为 n-1 的子问题。递归的终止条件是 n=1，此时直接执行移动操作。

代码实现

下面是基于 C++ 的完整实现。我们定义一个辅助函数 dfs 来处理具体的移动逻辑，主函数 hanota 负责初始化调用。

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;
        }
        // 将 n-1 个盘子从 A 移到 B，借助 C
        dfs(A, C, B, n - 1);
        // 将最大的盘子从 A 移到 C
        C.push_back(A.back());
        A.pop_back();
        // 将 n-1 个盘子从 B 移到 C，借助 A
        dfs(B, A, C, n - 1);
    }

    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        dfs(A, B, C, n);
    }
};