算法：汉诺塔问题的递归解法

题目：

有三根柱子，从左到右排列，编号分别是0、1、2。0号柱子上有n个盘子，从上到下，盘子依次增大，编号为1、2、3、···、n。现在需要将0号柱子上的盘子搬到右方编号为2的柱子上。有三条规则：

1. 一次搬一只盘子。
2. 每根柱子只有最上面的盘子可被搬动。
3. 大盘子不可置于小盘子的上方。

思路：

要想把0号柱子最底下的n号盘子放到2号柱子上，需要先把1～n-1号盘子移到1号柱子上。再把n号盘子移动到2号柱子上。然后再把1~n-1号盘子从1号柱子移动到2号柱子上。工作结束。那怎么把1~n-1号盘子移动到1号柱子上呢？这个问题和题目的问题是一样的，只是问题规模变小了，可以使用递归处理。

代码：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        hanotaRecursive(n, A,B,C);
    }
    void hanotaRecursive(int n, vector<int>& A, vector<int>& B, vector<int>& C) {
        if (n == 1) {
            C.emplace_back(A.back());
            A.pop_back();
            return;
        }
        hanotaRecursive(n - 1, A, C, B);
        C.emplace_back(A.back());
        A.pop_back();
        hanotaRecursive(n - 1, B, A, C);
    }
};