递归算法原理及经典例题讲解

1. 什么是递归

递归的本质是通过函数调用自身来实现问题的求解。设计递归通常包含以下步骤：

1. 确定问题可以被分解为多个重复子问题，且子问题与原问题具有相同的解决方法。
2. 找出子问题的共同点，从宏观角度看待问题。
3. 构建函数头，明确函数表示的含义及解决的问题。
4. 思考并设置递归的出口（结束条件）。递归出口必须在执行过程中被触发，防止死循环。

简单来说，递归是将大问题分解为小问题，直到达到基础情况再逐层返回结果的过程。

2. 具体例题讲解

2.1 LeetCode 面试题 08.06. 汉诺塔问题

问题描述：借助 B 柱子将 A 柱子上的盘子移动到 C 柱子上。

分析：当只有一个盘子时，直接移动；当有多个盘子时，先将 n-1 个盘子借助目标柱移到辅助柱，再将最大的盘子移到目标柱，最后将辅助柱上的 n-1 个盘子移到目标柱。

递归出口：当盘子数量为 1 时，直接移动并返回。

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) {
        dfs(a, b, c, a.size());
    }
};

2.2 LeetCode 21. 合并两个有序链表

问题描述：将两个有序链表合并为一个有序链表，不生成新链表节点。

分析：比较两个链表当前节点的值，较小的节点作为当前节点，其 next 指针指向剩余部分的递归结果。

递归出口：当其中一个链表为空时，返回另一个链表。