核心 · 算法第 6 课 / 共 8 课免费阅读

递归与归并排序 · 数据结构与算法

函数怎么能通过调用自己来解决问题？

课程目录

为什么需要它

有些问题里面藏着更小的同样的问题：文件夹里有文件夹，树里有子树，给列表排序可以变成给两半分别排序。递归能很自然地写出这些，它是归并排序、树的遍历以及大多数分治算法的基础。

直觉理解

每个递归函数都有两部分：

基本情况：问题小到可以直接回答（空列表、n = 0）。
递归情况：把问题变小，调用自己，再把答案组合起来。

相信更小的那次调用是对的，就像你相信 len() 一样。每次调用都在一个栈（调用栈）上等着，直到它的更小的调用返回。

归并排序：把列表分成两半，递归地给两半排序，再把两个有序列表合并：反复取两边队头中较小的那个。O(n log n)：拆分有 log n 层，每层合并要 n 的工作量。

定义

基本情况

The input a recursive function answers without calling itself. Without one, the calls never stop (RecursionError).
递归函数不调用自己就能直接回答的输入。没有它，调用永远停不下来（RecursionError）。

分治

Split a problem into independent smaller parts, solve each (often recursively), and combine the results.
把问题拆成互相独立的小部分，分别解决（通常用递归），再把结果组合起来。

示例

嵌套列表求和

动手试试

列表里可能有数字，也可能有更多的列表，嵌套任意多层。递归能处理这种嵌套。

def total(items):
    s = 0
    for x in items:
        if isinstance(x, list):
            s += total(x)
        else:
            s += x
    return s

print(total([1, [2, 3], [4, [5, 6]]]))

逐步执行

L4里面还有列表：交给一次更小的调用去加。
L7普通数字就是基本情况。
L101 + (2 + 3) + (4 + (5 + 6))。21

归并排序

动手试试

拆开、给两半排序、合并。

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))

print(merge([1, 4, 9], [2, 3, 10]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

逐步执行

L4取两边队头中较小的那个。
L10一边用完了；另一边剩下的已经是有序的。
L13基本情况：0 个或 1 个元素已经有序。
L19七个元素，拆了三层。[3, 9, 10, 27, 38, 43, 82]

常见错误

没有基本情况

总是调用自己的函数永远停不下来：RecursionError。先写基本情况。

问题没有变小

f(n) 调用 f(n)（而不是 f(n - 1)），永远到不了基本情况。

小测验

1. 这段代码会输出什么？

def countdown(n):
    if n == 0:
        print("go")
        return
    print(n)
    countdown(n - 1)

countdown(3)

A
```
3
2
1
go
```
B
```
go
1
2
3
```
C
```
3
2
1
0
```

查看答案

答案：A

每次调用打印自己的 n，再把 n − 1 交下去；0 是基本情况。

2. 为什么归并排序是 O(n log n)？

A拆半有 log n 层，每层合并要 n 的工作量
B它把每一对比较一次
C它是原地排序

查看答案

答案：A

拆半得到 log n 层；合并一层的所有列表，每个元素只碰一次。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出跟着调用走
准确写出这段程序的输出。
改需求加上基本情况
flatten(items) 应该把嵌套列表压平成一个列表，但它对数字也调用自己，结果崩溃了。修好它，让数字直接加进结果。
从零写合并两个有序列表
写函数 merge(a, b)，在 O(len(a) + len(b)) 时间内把两个有序列表合并成一个有序列表。不能调用 sorted() 或 .sort()。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Recursion	递归	A function solving a problem by calling itself on a smaller version.
Base case	基本情况	The smallest input, answered without recursion.
Merge sort	归并排序	Sort halves recursively, then merge them: O(n log n).