汉诺塔问题、递归与栈

01 | 引入

汉诺塔问题

在经典汉诺塔问题中，有 $3$ 根柱子及 $n$ 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面。移动圆盘时受到以下限制：

(1) 每次只能移动一个盘子；

(2) 盘子只能从柱子顶端滑出并移动到另一根柱子；

(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

在 LeetCode 汉诺塔问题中，三根柱子分别使用三个 vector<int> 表示：

A：起始柱；
B：辅助柱；
C：目标柱。

02 | 思路与题解

现有 $n$ 个圆盘，需要借助柱子 B 将它们从柱子 A 移动到柱子 C 。

我们可以先如何考虑把柱子 A 的最下方的最大的圆盘移动到柱子 C 的最下方，显然，这是这个过程中我们不得不做的一步。

那么，首先我们就必须要把最下方圆盘上方的所有圆盘都移动至柱子 B 。

因此整个问题可以拆成三步：

第一步：把上面的 $n - 1$ 个圆盘从 `A` 移动到 `B`

第二步：把最大的圆盘从 `A` 移动到 `C`

第三步：把 `B` 上的 $n - 1$ 个圆盘移动到 `C`

那么如何把 $n - 1$ 个圆盘移动到需要的地方呢？继续把这个问题拆分成三步，直到...

示范代码

class Solution {
public:
    void move(int n, vector<int>& A, vector<int>& B, vector<int>& C) {
        if (n == 0) return;

        // 1. 将 A 上面的 n-1 个圆盘移动到 B
        move(n - 1, A, C, B);

        // 2. 将 A 最下面的大圆盘移动到 C
        C.push_back(A.back());
        A.pop_back();

        // 3. 将 B 上的 n-1 个圆盘移动到 C
        move(n - 1, B, A, C);
    }

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

当 $n = 1$ 时，代码中的 move(n - 1, A, C, B); 和 move(n - 1, B, A, C); 退化为什么也不做。我们只需要将 A 最下面的大圆盘移动到 C, 就实现了将 A 上的所有圆盘移动到 C 的目标, 随即返回。

如果退出条件改成 $n = 1$ , 代码怎么写？

03 | 递归的思想

什么是递归？

若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；

若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

函数直接或间接调用自身，把大问题拆解成规模更小的相同子问题，直到到达基线条件（出口）停止。

补充：拆解得到两个或多个独立子问题叫做“分治”（Divide‑and‑Conquer，分而治之）。不是所有递归都是分治；分治一定是递归。如阶乘 $f (n) = n \cdot f (n - 1)$ ，只有 $1$ 个子问题，不是分治。

汉诺塔是一个非常典型的递归问题，我们发现，整个题目的要求、题解中的第一步、第三步都是在做相同的事情，但我们不断的缩小问题的范围，直至到达终止条件。

其核心思想可以抽象为思考：如果我们已经能正确地移动 $n - 1$ 个圆盘，那么移动 $n$ 个圆盘需要怎么做？

也就是：

利用递归，把 $n - 1$ 个圆盘移动到辅助柱；
移动最大的圆盘到目标柱；
再利用递归，把 $n - 1$ 个圆盘移动到目标柱。

递归还必须有终止条件。当： $n = 0$ 时，已经没有圆盘需要移动，因此直接返回。

Remark:这是不是很像数学归纳法？

考虑另一个问题：如何用递归求解 $n!$ 以及这么做有什么弊端？递归和迭代各有什么优劣？

04 | 递归过程与递归工作栈

递归过程在实现时，需要自己调用自己。

层层向下递归，退出时的次序正好相反。

每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。

每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。