一、递归：自己调用自己

算阶乘：5! = 5 × 4 × 3 × 2 × 1 = 120。 递归的写法是：要算 fact(5)，就算 5 × fact(4)；fact(4) 又算 4 × fact(3)……一直到 fact(1)。 演示里把它展开成 5 × 4 × 3 × 2 × 1。 展开这个动作很重要——递归的代码只有两行，但它干的事要展开才看得见。

为什么计算机能这么干？因为每次调用都新开一层「栈帧」，记住「我算到哪儿了、还差什么」。 这个「栈」就是 3.2 讲的堆栈。 所以递归不是魔法，它是拿堆栈当草稿纸，把「还没做完的事」记在上面。理解这一句，递归就不神秘了。

二、递归必须有两部分

演示里那句话是全篇的骨架：一个「什么时候停」的判断，一个「把问题缩小一点再交给自己」。 「什么时候停」叫终止条件。阶乘里是 n <= 1 返回 1。 「缩小一点」叫递归步。阶乘里是 n × fact(n-1)——n 变成 n-1，问题小了一点。

少任何一半都不行。 没有终止条件就是死循环；没有缩小，问题永远不变，终止条件永远碰不到。 这两句话可以当检查表用：写递归时先问「停在哪」，再问「每步是不是更近了」。 和第 4.5 那个「每一步是不是都在靠近终点」是同一个问法。

三、少了终止条件会怎样

演示里故意写了一个没有终止条件的递归： 调用了 197 次之后报错，RecursionError: maximum recursion depth exceeded。 为什么是 197 次而不是无限次？ 因为 Python 默认限制递归深度，大概一千层左右，演示里手动把上限调到 200 才打出这个数。 这个报错是好事。程序不是「算错」，是直接停住报错——至少你知道出事了。

对比一下另一种情况：如果那个错误不报错、只是算出一个错的数，你可能过一个月才发现。 报错是最便宜的失败方式。 所以「让它早失败」是工程上的一条原则。参数不对就报错，别默默用一个默认值兜过去。

四、同一件事，递归和循环各写一遍

斐波那契数列：1、1、2、3、5、8……每一项是前两项之和。 递归写法只有两行，看着极干净；循环写法要三个变量，看着笨。但跑起来差得离谱。

算第 20 个：递归调用了 21891 次，循环只跑了 20 次。 结果一样，代价差 1094 倍。 为什么差这么多？因为递归把同一个子问题算了一遍又一遍。 fib(20) 要 fib(19) 和 fib(18)，而 fib(19) 里又要算一次 fib(18)…… 演示里那句总结很准：fib(20) 里 fib(2) 被算了上千次。每一次都从头算，这就是浪费的来源。

五、递归适合什么场合

演示给的判据是：适合「问题能干净地二分」的场合，不适合「同一段反复重算」的场合。 归并排序、树遍历就属于前者：左边和右边是两块互不相干的数据，各算一次就够，不会重复。 斐波那契属于后者：子问题大量重叠，同一个值被反复求。

真要递归又怕重算，办法是记忆化：拿一个表把算过的记下来，下次先查表。 斐波那契加了记忆化，调用次数会从两万多次掉到二十次左右。 记忆化是动态规划的第一步。 它不改变递归的结构，只是不让它重复劳动。这跟 6.3 的 KMP「别丢已经算出来的信息」是同一条经验。

六、流程图：把算法画出来

演示里把「判断成绩等级」画成了流程图：开始，判 90 分以上，判 60 分以上，结束。 四种图形各管一件事：椭圆是开始或结束，矩形是做一件事，菱形是判断，箭头是下一步。 对应的代码也很好认：椭圆对应函数的第一行和 return，矩形对应赋值和计算，菱形对应 if 和 else。

流程图的价值不在好看，在画的时候会被迫想清楚：菱形有没有两个出口？每条路有没有走到结束？ 演示里那句总结是这一节最该带走的一句：这些在纸上画漏了，写代码时一定漏。

七、流程图画完，代码基本就写完了

为什么这么说？因为写代码难的地方从来不是敲键盘，是想清楚分支。 流程图逼你把三件事定下来：有哪几个判断、每个判断往哪走、走到哪儿停。这三件事定了， 剩下的就是翻译。 演示里给了个很实在的比例：这一步值得花五分钟，能省半小时调试。

本课那些复杂算法其实都能画出来：冒泡是一个双层循环加一个判断，二分是一个 while 加两个分支， 快排是一个分区加两次递归。 所以「画图」不是初学者的拐杖。越是复杂的逻辑，越值得先画出来再写。

八、动手 Demo：阶乘、斐波那契、流程图，三件事一起看

先写阶乘的递归版，看它两层结构（终止条件 + 缩小问题）。 再故意去掉终止条件，看它报什么错、调用了多少次。 最后把斐波那契的递归版和循环版各跑一遍，数清调用次数。

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

print('fact(5) =', fact(5))

import sys
sys.setrecursionlimit(200)
calls = 0
def bad(n):
    global calls
    calls += 1
    return bad(n + 1)
try:
    bad(0)
except RecursionError as e:
    print('调用了', calls, '次 ->', e)

def fib_r(n):
    global c2
    c2 += 1
    if n <= 2:
        return 1
    return fib_r(n - 1) + fib_r(n - 2)

def fib_l(n):
    a, b = 1, 1
    for _ in range(n - 2):
        a, b = b, a + b
    return a

for n in (10, 15, 20):
    c2 = 0
    print(n, fib_r(n), fib_l(n), '递归调用', c2, '次')

实跑输出：

--------------------------------------------------------------------
递归，以及算法怎么画成流程图
--------------------------------------------------------------------


  ① 递归：自己调用自己
  --------------------------------------------------------------------
  fact(5) = 120
  展开是：5 × 4 × 3 × 2 × 1
  递归函数必须有两部分：一个「什么时候停」的判断（n <= 1 返回 1），
  一个「把问题缩小一点再交给自己」（n × fact(n-1)）。少任何一半都不行。

  ② 少了终止条件会怎样
  --------------------------------------------------------------------
  写一个没有终止条件的递归：
    调用了 197 次之后 -> RecursionError: maximum recursion depth exceeded
  程序不是「算错」，是直接停住报错。这比算错好——至少你知道出事了。
  把递归上限调到 200 是为了这个演示不至于真的把内存吃光。

  ③ 同一件事，递归和循环各写一遍
  --------------------------------------------------------------------

| n | 递归结果 | 循环结果 | 一样吗 |
|---:|---:|---:|---|
| 10 | 55 | 55 | 一样 |
| 15 | 610 | 610 | 一样 |
| 20 | 6765 | 6765 | 一样 |

  算第 20 个：递归调用了 21891 次，循环只跑了 20 次
  结果一样，代价差 1094 倍。
  原因是递归把同一个子问题算了一遍又一遍——fib(20) 里 fib(2) 被算了上千次。
  所以递归适合「问题能干净地二分」的场合（归并排序、树遍历），不适合「同一段反复重算」的场合。
  真要递归又怕重算，就加个表把算过的记下来——那叫记忆化。

  ④ 流程图：把算法画出来
  --------------------------------------------------------------------
  判断成绩等级这件事，画成流程图是这样：

    [开始]
      ↓
    <分数 >= 90 ?> --是--> [等级 = 优] ----> [结束]
      ↓ 否
    <分数 >= 60 ?> --是--> [等级 = 及格] --> [结束]
      ↓ 否
    [等级 = 不及格] ----------------------> [结束]

| 图形 | 表示什么 | 代码里对应 |
|---|---|---|
| 椭圆 | 开始或结束 | 函数的第一行和 return |
| 矩形 | 做一件事 | 赋值、计算 |
| 菱形 | 判断 | if / else |
| 箭头 | 下一步去哪 | 执行的顺序 |

  流程图的价值在「画的时候就被迫想清楚」：菱形有没有两个出口、
  每条路有没有走到结束——这些在纸上画漏了，写代码时一定漏。
  流程图画完，代码基本就写完了。这一步值得花五分钟，能省半小时调试。

①fact 两行就完了：一行停、一行缩。所有递归都长这个形状。 ②bad 没有终止条件，一直往下调。 sys.setrecursionlimit(200) 是为了让它快点停，不至于真把内存吃光。 ③fib_r 里 c2 += 1 每进一次函数加一，所以最后数出来的就是总调用次数。第 20 个是 21891 次。 ④fib_l 用两个变量滚动，跑 20 次循环就完。结果一样，次数差 1094 倍。

30 秒实验

1. 给 fib_r 加一个字典当记忆表，看第 30 个要调用几次。
2. 把 bad 的 sys.setrecursionlimit 去掉，默认上限大概是多少次？
3. 用递归写一个「求列表最大值」，想想终止条件该写什么。

常见误区

1. 「递归比循环高级。」斐波那契上递归慢 1094 倍。它适合问题能干净二分的场合。
2. 「递归会算错。」少了终止条件它不报错才怪——它直接抛 RecursionError。
3. 「流程图是给初学者看的。」越是复杂逻辑越该先画，画漏的分支写代码时一定漏。

第 7 章到此结束。 最后一章往下钻一层：计算机到底用什么表示数。二进制的秘密、负数的补码、逻辑运算的规律， 都在第 8 章。

• ☐ （本篇完，下一篇 8.1 二进制、八进制与十六进制）

相关笔记

• 梯形法与埃氏筛
• 堆栈与队列
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引