递归算法核心原理与 LeetCode 实战解析

注意，递归出口通常置于函数首部，这是防止死循环的关键。

合并两个有序链表

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;
    }
  }
};

这里利用了函数头的定义：mergeTwoLists 本身就是负责合并的，所以直接让当前节点的 next 指向递归调用的结果即可。

反转链表

LeetCode 206. 反转链表 既可以用迭代（三指针），也可以用递归。

递归解法中，dfs 函数表示以当前节点为起点进行反转。

• 出口：遇到空节点或最后一个节点时返回。
• 逻辑：因为是单链表，需提前保存反转后的头节点（newnode）。递归返回后，将当前节点的下一个节点指向当前节点，并将当前节点的 next 置空。

/**
 * 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);
  }
};

补充一点，在递归过程中，中间层已经记录了上一层的节点信息，所以直接将当前节点指向空不会干扰前面的连接。

快速幂 Pow(x, n)

LeetCode 50. Pow(x, n) 要求手动实现幂运算。难点在于 n 可能为负数或很大。

利用分治思想：

• $2^{16} = 2^8 \times 2^8$
• $2^8 = 2^4 \times 2^4$

这样可以将时间复杂度从 $O(n)$ 降低到 $O( ext{log}n)$。

实现细节：

1. 使用 long long 存储指数，防止取反溢出。
2. 若 n 为负，将底数取倒数，指数转为正数。
3. 递归计算 myPow(x, 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;
    }
  }
};

这个判断逻辑对应了递归展开的最后一步，代码从底层向上回溯计算。

总结

学习递归的关键在于理解'自己调用自己'的过程，以及栈帧的展开与回溯。递归执行顺序是从上到下深入，再从下到上返回。

若仍感困惑，建议手绘递归展开图辅助理解，这有助于理清调用栈的变化。