如果你已经在递归里挣扎过一阵子，大概率会有这样的体验：单路递归很好懂，比如阶乘，一路算到底就行；可一旦某个函数在函数体里连续调用自己两次，脑子就开始打结。今天就用一个非常经典的例子——打印一把标尺，把这种“包含多个递归调用的递归”彻底讲清楚。标尺问题几乎是所有算法教材都会用的案例，它最大的价值就是逼你直面递归的执行顺序问题。看完这篇文章，你不仅能写出标尺代码，还能顺手把二叉树中序遍历、汉诺塔这类同构问题一并想明白。适合正在学数据结构、准备面试，或者写树形算法时总被递归绕晕的开发者。
1. 标尺问题为什么天然适合讲多递归
1.1 先看看标尺的刻度长什么样
尺子上的刻度是有规律的。以英制尺子为例，1 英寸的刻度线最长，1/2 英寸的次之，1/4 英寸的更短，1/8 英寸的再短一截。如果用横线数量代表刻度长度，一段 3 个单位长度的标尺，它的刻度模式长这样：
- -- - --- - -- -注意看这个序列：单数、双数、单数、三数、单数、双数、单数。中间最长的是 3，两边的结构完全对称；左侧的 1 和 2 之间的层级关系，和右侧一模一样。换句话说，一把 n 级标尺可以拆成“一把 (n-1) 级标尺 + 一条 n 级刻度线 + 另一把 (n-1) 级标尺”。
这个递归定义是天然自洽的：要画出 n 级标尺，先画左半段，再画中间那条主刻度，最后画右半段。而左半段本身又遵循同样的规则，只是规模小一档。这就是递归能把复杂图形压缩成三行代码的根本原因。
1.2 从单递归到多递归的跨越
阶乘或者斐波那契数列，都只有一个子问题：求 n! 依赖求 (n-1)!，求第 n 个斐波那契数依赖求第 n-1 和 n-2 个。但标尺问题不一样，一个 n 级标尺由两个独立的 (n-1) 级子标尺组成，也就是说，解决一个问题需要先解决两个性质相同、规模更小的子问题，再把结果拼起来。
体现在代码上，就是函数体内出现两次对自身函数的调用：
def ruler(n): if n == 0: return ruler(n - 1) # 第一次递归调用，处理左半段 print('-' * n) # 处理当前刻度 ruler(n - 1) # 第二次递归调用，处理右半段这就是“包含多个递归调用的递归”最典型的形态。很多第一次接触的人会以为两次调用会“同时发生”，其实完全不是。程序是顺序执行的，第一次调用会一直递归下去，直到它内部所有事情都处理完，才返回；然后执行当前这行的打印；接着再进入第二次调用。想通这一点，多递归调用就成功了一大半。
2. 核心实现：从最小版本到带标签版本
2.1 最小可运行版本
光说理论不够，直接上手跑代码。把上面的函数补充完整，并调用 n=3：
def ruler(n): if n == 0: return ruler(n - 1) print('-' * n) ruler(n - 1) ruler(3)运行结果就是前面展示的 7 行刻度线。可以试试 n=4，输出会变成 15 行：
- -- - --- - -- - ---- - -- - --- - -- -这个序列看起来是不是很像一把尺子的横截面？中间是 4，两侧对称分布 1、2、1、3、1、2、1。找到递归的感觉了吗：要画出 4 级标尺，先画出 1~3 的完整标尺，再画 4 的主刻度线，最后再画出 1~3 的完整标尺。
2.2 带刻度数字的版本
纯横线适合观察结构，但不好辨认每个刻度到底是几。可以把刻度数字一起打印出来，这样更直观。我通常写成这样：
def draw_line(tick, label=''): line = '-' * tick if label: line += ' ' + str(label) print(line) def ruler(n): if n == 0: return ruler(n - 1) draw_line(n, n) ruler(n - 1) ruler(3)输出结果：
- 1 -- 2 - 1 --- 3 - 1 -- 2 - 1这个版本在调试时更友好，因为每一行清清楚楚写了刻度等级。实际工程里如果想生成真正的尺子图形，还可以把横线改成竖线，或者叠加绘制毫米刻度，但核心递归逻辑完全一致。
2.3 基准情形与递归关系式
多递归调用最容易翻车的点是基准情形。标尺问题的基准情形很明确：当 n 等于 0 时，不需要画任何刻度，直接返回。注意不能写成if n == 1: print('-')，虽然那样也能跑出结果，但会破坏递归的自洽性，而且会导致 n=0 时永远无法收敛。
从调用次数上看，n 级标尺的调用次数满足递推关系：
- T(0) = 0
- T(n) = 2 * T(n-1) + 1
展开计算：
| n | T(n) | 输出行数 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 3 | 3 |
| 3 | 7 | 7 |
| 4 | 15 | 15 |
| 5 | 31 | 31 |
可以看到 T(n) = 2^n - 1。这个等式解释了为什么多递归调用的运行时间是指数级的：每增加一级，调用次数翻倍再加一。也正因为输出量本身是 2^n-1 行，所以这个指数级复杂度无法逃避。想验证自己的递归写得对不对，用递归关系式算一遍调用次数，和实际输出行数对比，是最快的检查手段。
3. 拆解执行过程：为什么输出顺序是这样
3.1 手工跟踪 n=3 的完整调用序列
理解多递归调用的关键是搞清楚“顺序”。我把 n=3 时函数完整执行过程展开一遍，所有细节都列出来：
- 进入 ruler(3)，n 不为 0，先执行第一次递归调用 ruler(2)。
- 进入 ruler(2)，先执行 ruler(1)。
- 进入 ruler(1)，先执行 ruler(0)。
- ruler(0) 命中基准情形，立即返回。
- ruler(1) 打印一行 '-'（长度 1）。
- ruler(1) 执行第二次 ruler(0)，直接返回。
- ruler(1) 执行完毕，回到 ruler(2)。
- ruler(2) 打印一行 '--'（长度 2）。
- ruler(2) 执行第二次 ruler(1)。
- 这个 ruler(1) 重复步骤 3~6，打印一行 '-'。
- ruler(2) 执行完毕，回到 ruler(3)。
- ruler(3) 打印一行 '---'（长度 3）。
- ruler(3) 执行第二次 ruler(2)，重复步骤 2~11，打印 '—'、'--'、'—'。
- ruler(3) 全部执行完毕。
每一步都严格对应“左递归 → 当前打印 → 右递归”的顺序。你会注意到，第一次递归调用不是简单“执行一下子函数”，而是把左半部分所有递归全部做完，才回到当前这层。正因为如此，最小的刻度 1 才会最先出现，而最大的刻度 3 出现在整个序列的正中间。
3.2 用一棵递归树看清全貌
把调用关系画成一棵递归树。这里不用任何花哨的图表工具，就用手工缩进就能表达：
ruler(3) ├── ruler(2) │ ├── ruler(1) │ │ ├── ruler(0) → return │ │ ├── print("-") │ │ └── ruler(0) → return │ ├── print("--") │ └── ruler(1) │ ├── ruler(0) → return │ ├── print("-") │ └── ruler(0) → return ├── print("---") └── ruler(2) ├── ruler(1) │ ├── ruler(0) → return │ ├── print("-") │ └── ruler(0) → return ├── print("--") └── ruler(1) ├── ruler(0) → return ├── print("-") └── ruler(0) → return整棵树的输出顺序，实际上就是树的中序遍历：先访问左子树，再访问根节点，最后访问右子树。每个节点代表一次函数调用；叶子节点是基准情形；内部节点是两个子调用中间的 println。这种“左子树 → 根 → 右子树”的遍历顺序，是二叉树中序遍历的镜面映射。理解了标尺，就理解了中序遍历。
3.3 一个帮助记忆的执行心理模型
很多人写多递归时，会不自觉地试图“同时推进”两条递归路径，这是最大的误区。正确的心智模型是这样的：把每一个递归调用看做一段普通的顺序代码，执行到ruler(n - 1)那一刻，当前函数剩余代码全部冻结，CPU 一头扎进子调用里，直到子调用完全结束，才回到当前函数继续执行冻结后的代码。
以主函数为例，它的代码是这样排列的：
ruler(n - 1) → 第一段：跑到地老天荒，把所有左半部分输出完 print(...) → 第二段：只在你回来后执行一次 ruler(n - 1) → 第三段：再跑去把右半部分输出完记住这个顺序：“第一个递归永远先执行完，第二个递归永远最后执行完，中间的打印永远卡在正中央”。有了这个画面，标尺问题的输出顺序就再也绕不晕你了。
4. 多递归调用最容易踩的坑与排查办法
4.1 坑：基准情形写错导致栈溢出
最常见的问题是把基准情形写成if n == 1。如果传入 n=0，函数会继续调用 ruler(-1)、ruler(-2)，永远无法收敛，最终抛出递归深度错误。标尺问题的基准情形必须处理 n=0，因为递归定义里“0 级标尺”就是空标尺。更安全的写法是if n <= 0: return，这样即使误传负数也不会无限递归。
4.2 坑：打印语句放错位置
把print放错位置是最隐蔽的问题。对比下面两个错误版本。
错误版本一：打印放在递归调用之前
def wrong_ruler(n): if n == 0: return print('-' * n) wrong_ruler(n - 1) wrong_ruler(n - 1)n=3 的输出是：
--- -- - - -- - -最大的 3 被最先打印出来，整个顺序乱成一团，完全没有左右对称的结构。错误版本二：打印放在两个递归调用之后
def wrong_ruler2(n): if n == 0: return wrong_ruler2(n - 1) wrong_ruler2(n - 1) print('-' * n)输出变成：
- - -- - - -- ---这次最大的 3 被拖到最后，变成了后序遍历。两个错误版本都缺少了中间的根刻度位置，导致标尺失去中心对称性。这从侧面说明：多个递归调用的相对位置不是风格问题，而是实质逻辑问题。
4.3 坑：误以为两个递归调用会并行执行
我在带人写递归时，几乎每个初学者都会问类似的问题：“两个 ruler(n-1) 是不是可以同时递归，一个画左边一个画右边？”答案是：除非你显式开启多线程，否则不会。普通函数调用是严格顺序的，第二个递归调用要等第一个递归调用彻底跑完才开始。试图通过“同时”理解这个算法，只会得到错误的时间复杂度模型和更混乱的调试思路。正确的时间复杂度模型就是上一节的 T(n)=2^n-1，每一次调用都是串行发生的。
4.4 调试技巧：给递归加缩进日志
当递归调用层数变多，光靠 print 看输出很难定位问题。我的习惯是给递归函数加一个缩进参数，把每次进入、打印、退出都打出来：
def ruler_debug(n, indent=0): pad = ' ' * indent print(f"{pad}enter ruler({n})") if n == 0: return ruler_debug(n - 1, indent + 2) print(f"{pad} print tick n={n}") ruler_debug(n - 1, indent + 2) print(f"{pad}exit ruler({n})")运行 n=2 时，输出清晰得多：
enter ruler(2) enter ruler(1) enter ruler(0) print tick n=1 enter ruler(0) exit ruler(1) print tick n=2 enter ruler(1) enter ruler(0) print tick n=1 enter ruler(0) exit ruler(1) exit ruler(2)看到没有，每一层都严格遵循“先左后自己再右”的顺序。如果你调试时发现某个 print 顺序不对，就对照这个日志，看是哪一层提前打印了。
4.5 坑：递归深度和 Python 默认限制
标尺问题的递归深度只有 n，不会因为调用次数多而栈溢出。但 Python 默认递归深度限制大约是 1000，所以如果执行ruler(1000)，即使理论上能输出 2^1000-1 行这种不可能完成的任务，程序也会立刻在递归层数上报错。这不是算法问题，而是语言限制。真要测试深层级，可以临时调高限制：
import sys sys.setrecursionlimit(2000)但说实话，标尺问题本身就不适合跑大 n，因为输出量是指数级。n=10 就有 1023 行，n=20 就超过一百万行，n=30 就超过十亿行。想观察规律用 n=4、n=5 足够，跑更大数值纯粹是在惩罚磁盘和终端。
5. 多个递归调用的通用套路与后续延伸
5.1 三种递归结构与三种遍历
标尺问题的代码结构是“递归调用 → 操作 → 递归调用”，操作夹在两个递归之间，对应中序遍历。如果你把代码结构调整一下，还能得到另外两种模式：
- 先操作、再两次递归：对应先序遍历，根节点先处理。
- 先两次递归、最后操作：对应后序遍历，子树先处理完再处理根。
很多初学者只记住了二叉树有三种遍历，却不知道这三种遍历的本质就是递归调用与“处理当前节点”语句的相对位置。把标尺问题彻底想通之后，二叉树前序、中序、后序遍历的代码一眼就能看懂，因为它们用的是完全相同的多递归结构。
5.2 汉诺塔：另一个双递归经典
汉诺塔问题也是标准的双递归：
def hanoi(n, src, helper, dst): if n == 0: return hanoi(n - 1, src, dst, helper) # 先把上面 n-1 个盘子移到辅助柱 print(f"move {src} -> {dst}") # 再把最底下的大盘子移到目标柱 hanoi(n - 1, helper, src, dst) # 最后把辅助柱上的 n-1 个盘子移到目标柱看到没有，和标尺问题的结构一模一样：一个递归调用在操作前，一个递归调用在操作后，中间是当前层的核心动作。汉诺塔移动次数 T(n)=2T(n-1)+1，也是 2^n-1，和标尺问题的调用次数完全相同。理解了标尺，你就掌握了汉诺塔的一半。
5.3 三个甚至更多递归调用的情况
标尺是双递归，但多递归不限于两次。现实中还会遇到三个递归调用的场景，比如三叉树的遍历、生成特定结构的所有组合。原理完全相同，只是递归树的每个节点分出三个分支。举个例子，写出 n 对括号的所有合法组合，就需要在递归函数里多次嵌套搜索，本质上也是多递归调用的变体。
遇到三递归时，执行顺序分析会复杂一些：第一个调用完整跑完，第二个调用再完整跑完，然后第三个调用，最后才是当前层的操作（取决于操作位置）。这时候手工跟踪已经不太现实，建议使用 4.4 节的缩进日志法，把每次调用的进入和退出打出来。
5.4 是否可以用迭代替代
标尺问题并非只能递归写。理论上可以用显式栈模拟递归过程，也可以用迭代方式生成整个序列，但代码复杂度会大幅提升。我的建议是：这个问题的价值不在“最优实现”，而在训练递归思维。真正值得投入精力的是理解执行顺序，而不是逃避递归。等你彻底理解了多递归调用，再去考虑用栈替换也来得及。
6. 写在最后的一段实操体会
我以前第一次认真抠这个例子时，最大的顿悟就在“第一个递归调用会一直执行到彻底完成”这句话上。在那之前，我总以为递归是某种能自动分层的神奇操作，直到我用带缩进的日志跑了一遍 n=3 才真正看清：程序每遇到一次调用，就要把当前工作搁置，完完整整跑完那个子调用，再回来继续。标尺问题之所以适合反复练，是因为它把递归的展开过程变成了肉眼可见的刻度线，错误时输出毫无对称感，正确时天然呈现美感。如果你写其他递归总是卡壳，找一张纸，把 n=3 的递归树亲手画一遍，再对照代码走一遍，通常比看十篇文章都管用。多递归调用其实没那么可怕，说到底就是“先处理左边，再处理中间，最后处理右边”这件小事，只是它在代码里反复嵌套了 n 层而已。
