递归

它是什么

递归 是一种把问题交给「更小的同类问题」的方法：函数 在运行中调用自己。要能停住，必须先写清退出条件（有时叫基础情形）；否则会一直调用下去，直到解释器拒绝。每一次调用都是一次新的过程，带着自己的参数和局部 变量。同名并不等于同一个正在跑的现场。

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

画 分形 树时，退出条件常常是层数为 0；递归步骤则是画一根枝，再在两侧画出更短的子树。有退出条件、并且每次都更接近它，就能停。危险的是条件写错，或缩小的量是 0。

名字从哪来

recursion 来自拉丁语 recurrere，「跑回去」。数学归纳法有同类气质：先处理 $n=0$ 或 $n=1$，再假定较小的情形已经成立。计算机科学把它写成函数调用，而不是纸上的「假设」。归纳法在纸上依赖读者同意「较小的已经成立」；递归在机器上依赖每一次调用都真正把问题缩小。

递归不是唯一的重复手段。循环 也能一遍遍做。能一眼看出「更小的同构问题」时，递归更短；只是在名单上从头走到尾时，循环更直白。

它怎么工作

一次合法的递归通常包含两块。退出条件：问题已经小到可以直接回答，不再调用自己。递归步骤：把问题缩小（长度变短、层数减 1、列表变短），调用自身，再用返回值或副作用拼出这一层的答案。用 海龟 作图时，还要在返回前把位置和朝向恢复，否则下一枝会接错。backward 和反向的 left / right 往往成对出现。子树画完，海龟不会自己回家。

递归和无限循环都可能「停不下来」，但报错不一样。无限 while 会一直占着运行；过深的递归会报 RecursionError。两者都说明退出条件没写对，或缩小步骤没有真正变小。画十层树若不用递归，可能要写十段几乎一样的代码；层数变成参数之后，规则是否仍是同一条，才变得可检验。

生活里在哪里

查词典：某个定义里还有词，再去查那个词，直到遇到已经认识的字。套娃：打开一个，里面还是同款更小的。手绘分叉的树：在每一枝的末端重复「再分两枝」，直到尺度小到不再下笔。这些过程若缺少「何时不再往下」，就会变成无法结束的手续。程序把那条停止条件写成可执行的判断，而不是靠耐心在中途放弃。

和相近概念的差别

循环在同一层环境里重复；递归每次进入新的调用，参数不同。分形描述对象的结构；递归是生成这种结构时常用的手段。抽象把「做什么」收成名字；递归是该名字在实现时调用自己。把「调用自己」直接等同于死循环，是跳过了退出条件这一半定义。

对话式编程 生成的递归草稿，最常见的缺陷恰恰是：看起来在缩小，实际缩小量为零；或画完子结构后没有恢复状态。能运行一层幸运的树，不等于规则在所有层数上成立。

常见误会

误会 1：调用自己就是死循环。

有退出条件、并且每次都更接近它，就能停。危险的是条件写错，或缩小的量是 0。

误会 2：n == 0 时还应该再画一点什么，否则「少一层」。

那一层本来就是「什么都不做」。把叶子画在退出条件里可以，但不要再调用自己。

误会 3：子树画完，海龟会自己回家。

不会。要写 backward。漏掉退回，是分形树最常见的设计缺陷。

想知道更多

• 书：艾伦·唐尼《像计算机科学家一样思考Python（第2版）》
• 书：布鲁克希尔《计算机科学概论》
• 书：埃里克·马瑟斯《Python编程：从入门到实践（第3版）》