递归算法实战：汉诺塔与合并有序链表详解

递归算法核心思维

很多人初次接触递归时，往往对代码的执行流程感到困惑甚至恐惧。其实理解递归的关键在于建立宏观视角：不要过度纠结函数调用自己的细节展开，而是相信函数的功能。

就像我们调用一个加法函数是为了利用它的计算能力一样，在递归中调用自身也是为了实现某个特定目标。以归并排序为例，mergesort 的功能是将无序数组变为有序。当我们调用 mergesort(left) 和 mergesort(right) 时，只需假设它们已经完成了各自部分的排序任务，剩下的工作就是合并这两个有序部分。这种'信任'是编写递归逻辑的基础，同时必须确保存在明确的递归结束条件，防止无限循环。

1. 汉诺塔

题目描述

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

解法思路

这是一个经典的递归问题。我们可以从简单情况推导：

• n=1：直接将盘子从 A 移到 C。
• n=2：借助 B 柱，先将小盘移到 B，大盘移到 C，最后小盘移到 C。
• n>2：策略一致。将 A 上 n-1 个盘子移到 B（借助 C），将最大的盘子移到 C，再将 B 上的 n-1 个盘子移到 C（借助 A）。

核心在于将规模为 n 的问题拆解为规模为 n-1 的子问题。当规模缩减到 1 时，直接执行移动操作。

C++ 实现

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

private:
    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);
    }
};

2. 合并两个有序链表

题目描述

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

解法思路

递归处理链表的核心在于定义好函数的职责：

1. 函数含义：接收两个链表的头结点，返回合并后的头结点。
2. 函数体：比较两个头结点的值，较小的那个作为当前合并链表的头，其 next 指针指向剩余部分的递归结果。
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) {
            // list2 的头节点更小，则将 list1 和 list2->next 放入该函数中实现两个链表的合并
            // 我相信函数能帮我实现出来，这也就是宏观视角看待递归
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else {
            // 同理 list1 的头节点更小也是如此
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

掌握递归的关键在于相信函数功能的宏观视角，避免陷入递归展开的细节泥潭。通过这两道经典题目，希望能帮助大家消除对递归的恐惧，建立起清晰的解题思路。