递归｜LeetCode 第一轮复盘

章节状态：第一轮已完成。LC 509 一遍完成；LC 344 使用双指针完成，并补充理解了递归表达；LC 24 起初没有思路，重点学习了链表递归中的“函数返回什么”；LC 50 的初始递归存在不收敛和效率问题。另以 LC 206 作为链表递归的补充对照。

一、第 3 组题目清单

顺序	LeetCode	难度	题目	核心训练	当前状态
1	509	简单	Fibonacci Number	基本情形、分支递归	一遍完成
2	344	简单	Reverse String	区间递归、递归前操作	双指针完成；递归已理解
3	24	中等	Swap Nodes in Pairs	链表递归、返回新头节点	重点复盘
4	50	中等	Pow(x, n)	快速幂、问题规模减半	重点复盘
补充	206	简单	Reverse Linked List	递归回溯、连接反转	对照复盘

二、递归的统一分析框架

写递归时，不应先想“代码怎样调用自己”，而应先回答下面六个问题。

1. 函数的契约是什么

递归函数接收什么，承诺返回什么？

例如：

swapPairs(head)

可以定义为：

接收一段链表的头节点，返回这段链表两两交换后的新头节点。

当前这一层只要相信较小问题会履行相同承诺，不必在脑中展开全部递归过程。

2. 基本情形是什么

基本情形是无需继续拆分、能够直接得出答案的最小输入。

Fibonacci：n 为 0 或 1
反转字符串：left >= right
两两交换链表：没有节点，或只剩一个节点
快速幂：指数为 0
反转链表：空链表，或只剩一个节点

缺少基本情形，递归通常不会停止；基本情形写错，则会漏掉边界输入或访问不存在的节点。

3. 问题规模是否严格缩小

每一次递归调用都必须更接近基本情形：

n       → n - 1
[l, r]  → [l + 1, r - 1]
head    → head.next
head    → head.next.next
n       → n // 2

仅仅“再次调用自己”不是递归进展。如果参数不变，例如：

self.myPow(x, n)  # n 没有变化

就会无限递归，直到 Python 抛出 RecursionError。

4. 较小问题是否仍是同一种问题

递归调用必须能够使用同一份函数契约。例如，交换前两个节点后，剩余的链表仍然是“对一段链表进行两两交换”；计算 x^n 时，x^(n // 2) 仍然是同一种幂运算问题。

5. 当前这一层需要做什么

递归不是把所有工作交给下一层。通常要把较小问题的结果与当前元素组合起来：

Fibonacci：将两个子问题的结果相加
反转字符串：交换当前两端
两两交换链表：交换当前两个节点并连接剩余结果
快速幂：将 half 与自身相乘
反转链表：把当前节点接到已反转后缀的末尾

6. 返回值代表什么

这是链表递归最容易遗漏的部分。递归返回的通常不是“操作是否完成”，而是处理后结构的入口：

swapPairs(head)    返回两两交换后的新头节点
reverseList(head)  返回完全反转后的新头节点

如果没有明确返回值含义，就很难知道当前层该如何重新连接节点，以及最终应该返回哪个节点。

三、LC 509. Fibonacci Number

递归写法

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1

        return self.fib(n - 1) + self.fib(n - 2)

为什么它适合说明递归结构

函数契约是“返回第 n 个 Fibonacci 数”。当 n >= 2 时，当前问题可以拆成两个相同类型的较小问题：

fib(n) = fib(n - 1) + fib(n - 2)

两个参数都在缩小，并最终到达 0 或 1。

为什么朴素递归不是高效解法

递归树中会重复计算相同子问题。例如 fib(5) 的两条分支都会计算 fib(3)。朴素递归的时间复杂度近似为 O(2^n)，递归栈空间为 O(n)。

可以使用记忆化将时间复杂度降为 O(n)，也可以用迭代把额外空间降为 O(1)。本题在这一组中的主要价值是理解基本情形与递归关系，不是说明递归一定是最佳实现。

四、LC 344. Reverse String

我的实现方向：双指针

class Solution:
    def reverseString(self, s: list[str]) -> None:
        left, right = 0, len(s) - 1

        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

这是本题更实用的写法：时间复杂度为 O(n)，额外空间为 O(1)。

为什么也能用递归解决

反转区间 [left, right] 可以分解为：

1. 交换最外侧的 s[left] 与 s[right]；
2. 递归反转更小的内部区间 [left + 1, right - 1]。

class Solution:
    def reverseString(self, s: list[str]) -> None:
        def reverse(left: int, right: int) -> None:
            if left >= right:
                return

            s[left], s[right] = s[right], s[left]
            reverse(left + 1, right - 1)

        reverse(0, len(s) - 1)

这里的递归关系是：

reverse(left, right)
= 交换两端 + reverse(left + 1, right - 1)

每次递归使待处理长度减少 2，最终到达空区间或单字符区间。

双指针与递归的关系

角度	双指针	递归
每轮动作	交换两端	交换两端
范围缩小	left += 1、right -= 1	参数变为 left + 1、right - 1
停止条件	left >= right	left >= right
时间复杂度	O(n)	O(n)
额外空间	O(1)	O(n) 调用栈

递归和双指针在逻辑上做的是同一件事，只是递归用调用栈保存每一层的 left、right。由于题目要求原地修改，并且字符串可能很长，双指针更合适。

五、LC 24. Swap Nodes in Pairs

最初的难点

看到“两两交换节点”时，它与 LC 206 的 Reverse Linked List 很像：两者都要修改 next。真正的难点不只是反转当前一条边，而是：

• 当前两个节点交换后，谁是这一段的新头？
• 当前这一对如何连接前面已经处理的部分？
• 当前这一对如何连接后面尚未处理的部分？
• 递归调用应该从哪个节点开始？

先定义递归函数的契约

swapPairs(head)

表示：

将以 head 开头的整段链表两两交换，并返回交换后的新头节点。

基本情形：

if head is None or head.next is None:
    return head

没有节点时无需交换；只剩一个节点时，该节点保持原样。

递归写法

class Solution:
    def swapPairs(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        if head is None or head.next is None:
            return head

        first = head
        second = head.next
        remaining = second.next

        swapped_remaining = self.swapPairs(remaining)

        second.next = first
        first.next = swapped_remaining

        return second

用 1 → 2 → 3 → 4 理解一层递归

当前这一层先识别：

first = 1
second = 2
remaining = 3 → 4

然后相信：

swapped_remaining = self.swapPairs(remaining)

会返回已经处理好的：

4 → 3

当前层只负责把 1、2 交换并接回去：

second.next = first              得到 2 → 1
first.next = swapped_remaining   得到 2 → 1 → 4 → 3

这一段交换后的新头是 second，因此返回 second，不是返回原来的 head。

为什么它与 Reverse Linked List 相似但不相同

它们都可以理解为“局部反转 + 重新连接”，但保持的结构不一样。

问题	每层处理几个节点	递归处理的剩余部分	当前层返回什么
LC 206 反转整条链表	1 个	head.next	整条反转链表的新头
LC 24 两两交换	2 个	head.next.next	当前交换后这一段的新头 second

LC 206 会把整条链表的方向全部反转；LC 24 只反转每个长度为 2 的局部区间，并保留各组之间的前后顺序。

迭代写法中的对应思想

class Solution:
    def swapPairs(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        dummy = ListNode(0, head)
        prev = dummy
        current = head

        while current is not None and current.next is not None:
            first = current
            second = current.next
            next_pair = second.next

            prev.next = second
            second.next = first
            first.next = next_pair

            prev = first
            current = next_pair

        return dummy.next

这里 prev 不是“前一个节点”这么模糊，而是“已经处理部分的尾节点”；current 是“下一组尚未处理节点的入口”。每轮同时维护当前组前方和后方的连接。

六、补充：LC 206. Reverse Linked List 的递归写法

class Solution:
    def reverseList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:

        if head is None or head.next is None:
            return head

        new_head = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return new_head

用 1 → 2 → 3 理解当前层

对于 head = 1，先相信：

new_head = self.reverseList(head.next)

已经把后缀 2 → 3 反转成：

3 → 2

此时原来的 head.next 仍然是节点 2，它已经是反转后缀的尾节点。于是：

head.next.next = head

让 2 指回 1：

3 → 2 → 1

随后必须执行：

head.next = None

断开原来的 1 → 2，否则 1 与 2 会形成环。最后返回的仍然是整条反转链表的新头 3，所以返回 new_head。

LC 206 与 LC 24 的递归对照

关注点	LC 206	LC 24
函数契约	返回完全反转后的新头	返回两两交换后的新头
基本情形	少于 2 个节点	少于 2 个节点
递归入口	head.next	head.next.next
当前层动作	把当前节点接到反转后缀末尾	交换当前两个节点并连接后缀
返回值	new_head	second

共同点是：先明确递归调用返回的是一段已经处理好的链表，再由当前层完成边界处的连接。

七、LC 50. Pow(x, n)

我的原始代码

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n == 1:
            return x
        if n < 0:
            return 1 / self.myPow(x, n)

        return x * self.myPow(x, n - 1)

问题一：负指数分支没有缩小问题

当 n < 0 时：

return 1 / self.myPow(x, n)

递归调用仍传入完全相同的 x 和 n。例如：

myPow(2, -3)
→ 1 / myPow(2, -3)
→ 1 / (1 / myPow(2, -3))
→ ...

它永远不会到达 n == 0 或 n == 1，最终触发 RecursionError。

负指数应先转化为正指数：

x^(-n) = (1/x)^n

因此可以执行：

if n < 0:
    x = 1 / x
    n = -n

问题二：正指数虽然数学正确，但规模缩小太慢

return x * self.myPow(x, n - 1)

能够正确表达 x^n = x × x^(n-1)，但需要递归 n 层，时间复杂度和调用栈空间都是 O(n)。当 n 很大时会超时或超过 Python 的递归深度限制。

快速幂的核心

将指数每次减 1，只消去一个单位；将指数每次除以 2，才能真正形成对数级递归。

n 为偶数：x^n = (x^(n/2))²
n 为奇数：x^n = (x^(⌊n/2⌋))² × x

正确写法

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n

        def power(exp: int) -> float:
            if exp == 0:
                return 1.0

            half = power(exp // 2)

            if exp % 2 == 0:
                return half * half
            return half * half * x

        return power(n)

为什么要先保存 half

正确：

half = power(exp // 2)
return half * half

如果写成：

return power(exp // 2) * power(exp // 2)

就会对同一个子问题递归计算两次，使递归树重新产生大量重复计算，失去快速幂的效率优势。

快速幂的时间复杂度为 O(log |n|)，递归栈空间为 O(log |n|)。

八、四道题的递归形态对照

题目	每层递归次数	下一层规模	当前层的工作	主要风险
LC 509 Fibonacci	2 次	n-1、n-2	两个结果相加	重复子问题
LC 344 Reverse String	1 次	区间长度减 2	交换两端	调用栈并非 O(1)
LC 24 Swap Pairs	1 次	链表减少 2 个节点	交换一对并接回后缀	返回错头节点、断链
LC 50 Pow	1 次	n // 2	平方，奇数时再乘 x	参数不变、重复递归
LC 206 Reverse List	1 次	链表减少 1 个节点	当前节点接到后缀末尾	忘记断开旧连接而成环

九、本轮暴露出的关键遗漏

1. 递归调用必须保证进展

检查每个会继续递归的分支，确认参数都严格靠近基本情形。LC 50 的负指数分支正是因为 n 完全没有变化而无限递归。

2. 能使用递归，不等于递归是最佳实现

LC 344 可以自然地递归表达，但双指针空间更好；LC 509 可以递归定义，但朴素递归包含严重的重复计算。选择实现时还要评估时间复杂度、调用栈和语言限制。

3. 链表递归首先要确定“返回哪个头”

LC 24 交换 first 与 second 后，新头是 second；LC 206 完全反转后，新头来自最深层递归返回的 new_head。如果函数契约含糊，连接关系和返回值很容易同时出错。

4. 修改 next 前后都要检查链表可达性

修改指针前要保存仍需访问的后续节点；修改指针后要确认：

• 新头节点是谁；
• 所有需要保留的节点是否仍然可达；
• 是否形成了意外的环；
• 当前处理结果是否已经连接到递归返回的后缀。

5. 先相信函数契约，再分析当前一层

理解递归时无需同时追踪全部调用层。可以暂时假设较小输入已经被正确处理，然后只回答：当前层拿到这个结果后，要做什么才能构成当前输入的答案？完整展开只用于验证，不应成为设计递归的主要方法。

6. 注意工作发生在递归之前还是之后

LC 344：先交换两端，再递归内部区间
LC 24：可以先递归处理后缀，再交换并连接当前一对
LC 206：必须先得到反转后缀，再在回溯阶段反转当前连接
LC 50：先得到 half，再在回溯时组合结果

操作顺序由函数契约和数据依赖决定，不是固定模板。

十、写递归前的检查清单

1. 我能用一句话说明这个函数保证返回什么吗？
2. 哪些最小输入可以直接返回？
3. 所有递归分支的参数都严格缩小了吗？
4. 缩小后的问题仍然是同一种问题吗？
5. 当前这一层是在递归前操作，还是在递归返回后组合？
6. 如果有多个递归调用，是否重复计算了相同子问题？
7. 返回值是数值、布尔值，还是修改后结构的新入口？
8. 修改链表连接前，是否保存了后续入口？
9. 时间复杂度由递归深度决定，还是由分支数量共同决定？
10. 最大递归深度是否可能超过 Python 的限制？

十一、隔两到三天后的验收

不要看本文，从空白完成：

1. 写出 LC 509 的递归解法，并说明它为什么会重复计算。
2. 分别用双指针与递归完成 LC 344，并比较空间复杂度。
3. 写出 LC 24，说明递归函数的返回值为什么是交换后链表的新头。
4. 写出 LC 50 的快速幂，解释为什么指数必须减半，以及为什么只递归计算一次 half。
5. 口头推演 LC 206 的递归写法，解释 head.next.next = head 与 head.next = None 各自的作用。

如果能够从函数契约出发独立设计基本情形、缩小方式、当前层操作和返回值，并能判断递归复杂度，而不是只记住代码形状，才算完成这一轮递归训练。