汉诺塔问题递归解法（C++代码详解） 牛客4414题解题指南

一、题目解读

汉诺塔问题是一个经典的递归算法题目：有n个大小不同的圆盘按从大到小顺序放在柱A上，需借助柱B，将圆盘移至柱C，每次只能移动一个圆盘，且大圆盘不能置于小圆盘之上。牛客4414题要求编写函数输出移动步骤，考验递归思维与逻辑拆解能力。

二、解题思路

采用递归策略，核心思想为“分解与合并”：

1. 递归基情况：当n=1时，直接移动单个圆盘。

2. 递归步骤：

    将n个圆盘分解为两部分——n-1个小圆盘与最底层大圆盘。

    递归调用：将n-1个圆盘从柱A移至柱B（借助柱C）。

    移动大圆盘：将最底层圆盘从A移至C。

    再次递归：将B上的n-1个圆盘移至C（借助A）。

    通过层层递归，将大问题分解为子问题，最终合并子结果得到完整解。

三、解题步骤

1. 边界处理：代码中判断n是否在[1,16]范围内，超出则返回空结果。

2. 递归调用：hanoi(n-1, from, aux, to, moves)实现n-1圆盘移动，递归深度随n递减。

3. 关键步骤记录：每次移动最底层圆盘时，通过moves.push_back()保存步骤描述。

4. 递归回溯：完成子任务后，递归栈逐层返回，组合所有步骤至moves向量。

四、代码与注释

class Solution {
public:
    void hanoi(int n, string from, string to, string aux, vector<string>& moves) {
        if (n == 1) {  // 基情况：直接移动单个圆盘
            moves.push_back("move from " + from + " to " + to);
            return;
        }
        // 递归步骤1：将n-1个圆盘从from移至aux（借助to）
        hanoi(n - 1, from, aux, to, moves);
        // 移动最底层圆盘
        moves.push_back("move from " + from + " to " + to);
        // 递归步骤2：将aux的n-1个圆盘移至to（借助from）
        hanoi(n - 1, aux, to, from, moves);
    }

    vector<string> getSolution(int n) {
        vector<string> moves;
        if (n < 1 || n > 16) return moves;  // 边界检查
        hanoi(n, "left", "right", "mid", moves);  // 初始化递归
        return moves;
    }
};

五、总结

1. 递归优势：将复杂问题分解为简单子问题，代码简洁但需理解调用栈逻辑。

2. 时间复杂度：O(2^n)-1次移动（忽略边界情况），效率随n指数增长，适用于中小规模问题。

3. 优化方向：可进一步优化步骤描述或采用非递归实现（如迭代），但递归更易理解。

4. 关键技巧：明确基情况与递归步骤的拆分逻辑，确保每次移动满足规则。