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

注意：递归出口通常写在最前面，防止死循环。

LeetCode 21. 合并两个有序链表

题目要求将两个有序链表合并为一个，不可再生成新链表。

直接在原函数中递归：

• 出口：当一个链表为空时，返回另一个链表。
• 逻辑：比较两链表当前节点值，较小者作为当前节点，其 next 指向剩余部分的递归结果。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

LeetCode 206. 反转链表

题目要求翻转链表。解法包括递归和三指针。

递归实现：

• 函数头表示当前需要反转的节点。
• 出口：遇到最后节点或空节点时返回。
• 单链表需提前保存最后一个节点位置（newnode）。
• 逻辑：当前节点的下一个节点指向当前节点，当前节点指向空。

/**
 * 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* dfs(ListNode* l1) {
        if (!l1 || !l1->next) return l1;
        ListNode* newnode = dfs(l1->next);
        l1->next->next = l1;
        l1->next = nullptr;
        return newnode;
    }
    ListNode* reverseList(ListNode* head) {
        return dfs(head);
    }
};

LeetCode 50. Pow(x, n)

手动实现 pow 函数。n 可能为负数或很大，需注意处理。

发现重复子问题：2 的 16 次方可由两个 2 的 8 次方相乘得到。

代码实现：

• m 赋值给 long long 类型以防溢出。
• 若 m 为负数，x=1/x，n 转为正数。
• 递归计算 n/2 次幂，根据奇偶性返回结果。

class Solution {
public:
    double myPow(double x, int m) {
        long long n = m;
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        if (n == 0) return 1.0;
        double tmp = myPow(x, n / 2);
        if (n % 2 == 0) {
            return tmp * tmp;
        } else {
            return tmp * tmp * x;
        }
    }
};

总结

学习递归算法需理解'自己调用自己'的过程。递归执行是从底向上返回，存在从小到大、从后到前的过程。若难以理解，建议绘制递归展开图辅助分析。