算法题讲解：递归思想实战——汉诺塔与合并有序链表

递归，搜索与回溯算法前置知识

理解递归的关键在于明确函数的功能定义。递归的本质是自己调用自己，就像调用普通函数一样，我们只需关注它'能做什么'，而不必纠结于内部如何一步步执行。

以归并排序为例，mergesort 的功能是将无序数组变为有序。在实现时，我们假设递归调用 mergesort(nums, left, mid) 后左半部分已有序，同理右半部分亦然，随后只需合并两者即可。这种宏观视角能有效避免陷入递归深度的细节泥潭。当然，必须确保存在递归终止条件。

1. 汉诺塔

题目描述

有三根柱子 A、B、C，A 柱上有 n 个大小不同的圆盘，从小到大叠放。要求将 A 柱上的所有圆盘移动到 C 柱上，移动过程中大盘子不能压在小盘子上面，且每次只能移动一个盘子。

题目示例

解法 (递归)

算法思路

这是一道递归方法的经典题目，我们可以先从最简单的情况考虑：

1. 假设 n=1：只有一个盘子，直接把它从 A 移到 C。
2. 如果 n=2：借助 B 柱。先将 1 号盘子放到 B，再将 2 号盘子放到 C，最后将 1 号盘子放到 C。
3. 如果 n>2：利用 n=2 时的策略。将 A 上面的 n-1 个盘子挪到 B 上，再将最大的盘子挪到 C 上，最后将 B 上的小盘子挪到 C 上。

则本题可以被解释为：

• 对于规模为 n 的问题，我们需要将 A 柱上的 n 个盘子移动到 C 柱上。
• 规模为 n 的问题可以被拆分为规模为 n-1 的子问题：
  • 将 A 柱上的上面 n-1 个盘子移动到 B 柱上。
  • 将 A 柱上的最大盘子移动到 C 柱上，然后将 B 柱上的 n-1 个盘子移动到 C 柱上。
• 当问题的规模变为 n=1 时，即只有一个盘子时，我们可以直接将其从 A 柱移动到 C 柱。

需要注意的是，步骤 2.b 考虑的是总体问题中的子问题 b 情况。在处理子问题的子问题 b 时，我们应该将 A 柱中的最上面的盘子移动到 C 柱，然后再将 B 柱上的盘子移动到 C 柱。在处理总体问题的子问题 b 时，A 柱中的最大盘子仍然是最上面的盘子，因此这种做法是通用的。

C++ 算法代码

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& x, vector<int>& y, vector<int>& z, int n) {
        if (n == 1) { // 递归结束条件：x 柱中只有一个盘子，直接放到 z 柱即可
            z.push_back(x.back());
            x.pop_back();
            return;
        }
        // 先将 n-1 个盘中利用 z 柱放到 y 柱上
        dfs(x, z, y, n - 1);
        // 再将 x 柱中最底下的盘中放到 z 柱上
        z.push_back(x.back());
        x.pop_back();
        // 最后将 y 柱上 n-1 个盘子利用 x 柱放到 z 柱上
        dfs(y, x, z, n - 1);
        return;
    }
};

算法总结及流程解析

2. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目示例

解法 (递归)

算法思路

1. 递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点。
2. 函数体：选择两个头结点中较小的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理。
3. 递归出口：当某一个链表为空的时候，返回另外一个链表。

注意：链表的题一定要画图，搞清楚指针的操作！

C++ 算法代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 递归的结束条件为当其中一个链表走到头，返回另一个链表当前递归位置
        if (list1 == nullptr) {
            return list2;
        }
        if (list2 == nullptr) {
            return list1;
        }
        if (list1->val > list2->val) {
            // list1 的头节点更小，则将 list1->next 和 list2 放入该函数中实现两个链表的合并
            // 合并后就变成有序的了，返回的结点再于 list1 头节点相连则完成了合并
            // 具体 list1->next 和 list2 放入函数后怎么合并成有序我不管
            // 我相信函数能帮我实现出来，这也就是宏观视角看待递归
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else {
            // 同理 list2 的头节点更小也是如此
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

算法总结及流程解析