递归算法：原理、设计与经典例题解析

什么是递归

递归的本质是通过函数调用自身来实现问题的求解。其代码通常较为简洁，设计递归需遵循以下步骤：

1. 确定问题可被分解为多个重复子问题，且子问题具有与原问题相同的解决方法。
2. 提取子问题的共同点，从宏观角度看待问题。
3. 构建函数头，明确函数解决的问题。
4. 思考递归的出口（终止条件）。递归出口是必须的，且在执行过程中一定会触发。

简单来说，当一个问题可以不断分化成小问题时，即可使用递归算法。

具体例题讲解

LeetCode 面试题 08.06. 汉诺塔问题

题目要求借助 B 柱子将 A 上的盘子移动到 C 上。

观察不同数量的盘子情况：

• 1 个盘子：直接从 A 移到 C。
• 2 个盘子：借助 C 将 A 上盘子移至 B，将 A 最大盘移至 C，再将 B 上盘子移至 C。
• 3 个盘子及以上：同理，通过中间柱子转移 n-1 个盘子。

递归出口：当 A 或 B 上只有一个盘子时，直接将其放到 C 并返回。

class Solution {
public:
    void dfs(vector<int>& x, vector<int>& y, vector<int>& z, int n) {
        if (n == 1) {
            z.push_back(x.back());
            x.pop_back();
            return;
        }
        dfs(x, z, y, n - 1);
        z.push_back(x.back());
        x.pop_back();
        dfs(y, x, z, n - 1);
    }
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        (a, b, c, a.());
    }
};