上一课讲排序时，我们偷偷用了一个"作弊"的招数：归并排序里，函数自己调用了自己——merge_sort 里面又调 merge_sort。

这招有个正式的名字，叫递归（recursion）。它是算法世界里最优雅、也最让人头疼的思想之一：写对了代码短得惊人，写错了递归爆栈、死循环。这一课，我们把递归和它最经典的搭档——分治——彻底讲透。

一、递归是什么：函数自己调用自己

先看一个最简单的例子——算阶乘 n!。

def factorial(n):
    if n == 0:           # 边界：0! = 1
        return 1
    return n * factorial(n - 1)   # 递归：n! = n × (n-1)!

print(factorial(5))   # 120

它干了什么？factorial(5) 想算 5!，但它不自己算，而是说"5! = 5 × 4!"，把 4! 甩给 factorial(4)；factorial(4) 又说"4! = 4 × 3!"……一路甩下去，直到 factorial(0) 说"这个我知道，等于 1"，然后一层层把答案往回传。

递归 = 把大问题，变成一个"规模更小的同类型问题"，直到小到能直接回答。

二、递归三要素：缺一不可

写递归，脑子里必须时刻钉着三件事：

1. 边界条件（base case）——什么时候停

递归必须有个"能直接回答、不再调用自己"的出口。没有它，就是死循环，最后爆栈。

if n == 0:      # 这就是边界
    return 1

2. 递推关系（recursive case）——怎么往小里走

每一层，都要让问题变小，并且一步步逼近边界。

return n * factorial(n - 1)   # n 变小了，往 0 逼近

如果问题不缩小（比如 f(n) 又调 f(n)），就是死循环。这是新手最常犯的错。

3. 返回值——怎么把答案传回来

递归不是光往下钻，钻到底后，答案要一层层返回来。factorial(5) 依赖 factorial(4) 的结果，所以要 return，让结果能往上冒。

三要素：边界让它停，递推让它小，返回让它能传回答案。 写任何递归前，先想清这三条。

三、调用栈：递归背后的"隐形助手"

递归为什么能工作？靠的是调用栈（call stack）——还记得第 2 课讲的栈吗？后进先出。

每调一次函数，就把这一层的"现场"（n 的值、算到哪了）压进栈；函数返回时，弹出栈顶，回到上一层继续。

factorial(5)  压栈
  factorial(4)  压栈
    factorial(3)  压栈
      ...
        factorial(0)  → 返回 1  弹栈
      factorial(1) → 返回 1     弹栈
    factorial(2) → 返回 2       弹栈
  ...
factorial(5) → 返回 120

栈的深度，就是递归的层数。 这解释了一个致命问题：

# 递归算斐波那契，n 一大就卡死
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))   # 要算几十秒！因为大量重复计算

为什么 fib(40) 这么慢？因为 fib(40) 调 fib(39) 和 fib(38)，而 fib(39) 又调 fib(38)……同一个 fib(38) 被算了两次，fib(37) 被算了三次，重复计算爆炸式增长，复杂度是恐怖的 O(2ⁿ)。

这引出后面要讲的关键武器——记忆化：把算过的结果存起来，别重复算。

# 用字典记住算过的值，fib(40) 瞬间完成
cache = {0: 0, 1: 1}
def fib_memo(n):
    if n not in cache:
        cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]

print(fib_memo(40))   # 102334155，瞬间出结果

四、分治：递归的"战术级"应用

分治（divide and conquer） 是递归最经典的用法，套路固定三步：

分（Divide）：把大问题拆成几个小问题；
治（Conquer）：分别解决小问题（通常递归）；
合（Combine）：把小问题的答案合并成大问题的答案。

上一课的归并排序，就是完美的分治：

def merge_sort(nums):
    if len(nums) <= 1:          # 治：小到不用拆
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])    # 分 + 治：递归排左半
    right = merge_sort(nums[mid:])   # 分 + 治：递归排右半
    return merge(left, right)        # 合：合并两个有序段

分治的威力在于：把 O(n²) 的问题，变成 O(n log n)。 每次拆一半，拆出 log n 层，每层花 O(n) 合并。

经典分治题：求数组最大值（复习 + 新角度）

第 1 课我们见过"找最大值"，那是 O(n) 一遍扫。换个分治写法，体会一下"拆小"：

def max_dc(nums, low, high):
    if low == high:                  # 只有一个元素，直接返回
        return nums[low]
    mid = (low + high) // 2
    left_max = max_dc(nums, low, mid)       # 分：左半最大
    right_max = max_dc(nums, mid + 1, high) # 分：右半最大
    return max(left_max, right_max)         # 合：取两者更大

nums = [3, 9, 1, 7, 5]
print(max_dc(nums, 0, len(nums) - 1))   # 9

它比一遍扫的 O(n) 慢（常数更大），但思路是万能模板：很多问题"整体难、拆开简单"，分治就是那把钥匙。

五、主定理：分治复杂度的"直觉版"

你可能好奇：归并排序 O(n log n)，快排 O(n log n)，那别的分治呢？有没有个公式？

有，叫主定理（Master Theorem）。你不需要背公式，记住这个直觉就够用：

每次把问题拆成 a 个子问题、每个子问题规模是原来的 1/b，合并的代价是 O(n^d)。那么：

  • 如果 a = b^d → 复杂度是 O(n^d · log n)（如归并：a=2, b=2, d=1，所以 O(n log n)）
  • 如果 a < b^d → 合并占大头，复杂度 O(n^d)
  • 如果 a > b^d → 子问题占大头，复杂度 O(n^(log_b a))

换个说法：拆出来的活儿和合并的活儿谁更重，复杂度就由谁主导。归并是"拆两半 + 合并 O(n)"，两边势均力敌，所以乘上 log n。

六、递归的两个"亲戚"：尾递归 & 递归转迭代

尾递归：把递归变成"换个参数重跑"

如果递归的最后一件事就是调用自己（没有额外的 n * ... 要做），就叫尾递归。它有个好处：编译器可以优化成循环，不爆栈。

# 普通递归：返回时要"乘以 n"，所以不是尾递归
def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

# 尾递归：把中间结果用参数"累加"着传下去
def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, acc * n)   # 最后一步就是调自己，无额外计算
注意：Python 官方解释器没有做尾递归优化，所以尾递归在 Python 里该爆栈还是会爆栈。但这个思想很重要——它揭示了"递归和循环其实是同一件事的两种写法"。

递归转迭代：任何递归都能写成循环

既然递归靠调用栈，那我们自己拿个栈手动模拟，就能把递归改成循环。斐波那契就是最典型的例子：

# 递归版（重复计算，O(2ⁿ)）
def fib_rec(n):
    return n if n <= 1 else fib_rec(n - 1) + fib_rec(n - 2)

# 迭代版（自底向上，O(n)）
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_rec(10), fib_iter(10))   # 55 55

心法：递归是"自上而下"（从大问题往下拆），迭代是"自下而上"（从小答案往上垒）。很多递归题，改成自底向上的迭代，就顺手过渡到了动态规划——那是第 17 课的主角，现在先混个脸熟。

七、复杂度小结

场景复杂度说明
普通递归（如 factorial）O(n)每层只调一次自己
朴素斐波那契O(2ⁿ)重复计算爆炸
记忆化斐波那契O(n)算过的存起来
归并排序O(n log n)拆两半 + O(n) 合并
分治找最大O(n)每层合并 O(1)

八、动手时间 🎯

实验 1：观察朴素斐波那契的"卡顿"

import time

def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

for n in [10, 20, 30, 35]:
    start = time.time()
    fib(n)
    print(f"fib({n}) 耗时:", round(time.time() - start, 4), "秒")

你会看到：每加 1，时间几乎翻倍——这就是 O(2ⁿ) 的恐怖。n 到 35 就已经要等一会儿了。

实验 2：记忆化救场

from functools import lru_cache

@lru_cache(maxsize=None)   # Python 内置的记忆化神器
def fib_memo(n):
    return n if n <= 1 else fib_memo(n - 1) + fib_memo(n - 2)

start = time.time()
print(fib_memo(200))
print("fib(200) 耗时:", round(time.time() - start, 4), "秒")   # 瞬间

@lru_cache 就是给函数套了个"记住结果"的字典，一行搞定记忆化。

实验 3：用递归反转字符串

def reverse(s):
    if len(s) <= 1:
        return s
    return reverse(s[1:]) + s[0]   # 反转 = 反转剩下的 + 第一个放最后

print(reverse("hello"))   # 'olleh'

实验 4（挑战）：汉诺塔

三根柱子，把 n 个大小不同的圆盘从 A 柱移到 C 柱，规则：一次只能移一个，大的不能压小的。递归思路经典到爆：

def hanoi(n, a, b, c):   # 把 n 个盘从 a 借助 b 移到 c
    if n == 1:
        print(f"{a} -> {c}")
        return
    hanoi(n - 1, a, c, b)   # 先把上面 n-1 个从 a 借 c 移到 b
    print(f"{a} -> {c}")    # 最大的一个从 a 移到 c
    hanoi(n - 1, b, a, c)   # 再把 b 上 n-1 个借 a 移到 c

hanoi(3, "A", "B", "C")

跑一下，看它打印的移动步骤。体会：你压根没写"具体怎么一步步挪"，只是说清了"大问题拆成两个小问题 + 挪一个"，它就自动完成了——这就是递归的优雅。

九、小结

  1. 递归 = 函数自己调用自己，三要素：边界让它停、递推让它小、返回让答案能传回。
  2. 分治是递归的战术应用——分、治、合三步，把 O(n²) 砍成 O(n log n)；主定理记直觉"拆的活和合的活谁重谁主导"。
  3. 递归的敌人是重复计算和爆栈——用记忆化（@lru_cache）干掉重复，用"自底向上迭代"绕开爆栈，这两招也是通往动态规划的桥。

先别急着往后翻，把斐波那契的"卡顿 vs 记忆化"和汉诺塔敲熟，递归的手感就长在你脑子里了。

标签: none

添加新评论