后面每一章都是「暴力很慢 → 想出关键一步 → 正解很快」。 这一章不比快慢 —— 它要解决的是一个更靠前的问题：你为什么读得懂递归、却写不出递归。
所以这里故意挑了一道用循环三行就能搞定的题。因为循环版你百分之百写得对， 它就能当成标准答案，让你验证自己写的递归到底对不对。先建立信任，再谈技巧。
1 一句话问题
给一个非负整数 n，求它各位数字之和。
输入 12345
输出 15 因为 1 + 2 + 3 + 4 + 5 = 152 先用纸笔手算一遍
拿 12345 手算，把每一步写下来：
12345 的数位和 = 5 + (1234 的数位和)
1234 的数位和 = 4 + (123 的数位和)
123 的数位和 = 3 + (12 的数位和)
12 的数位和 = 2 + (1 的数位和)
1 的数位和 = 1 + (0 的数位和)
0 的数位和 = 0 ← 到底了请务必真的在纸上写一遍。写完盯着这六行看，你会发现一件事：
每一行的形状都一模一样，都是「最后一位 + 剩下那部分的数位和」。 唯一特殊的是最后一行 —— 它不需要问别人，自己就知道答案是 0。
这六行就是递归。不是「像」递归，它就是。剩下的只是把它翻译成 C++。
3 循环写法（你已经会的那种）
点「运行 ▶」看结果
没什么好说的，这个你闭着眼睛都能写。但请记住它 —— 第 10 步我们要拿它当标准答案。
4 先确认它是对的
改几个输入试试：0、7、100、999999999。特别是 0，它是最容易被忽略的边界。
确认无误之后，我们就有了一份可信的参照物。这一点很重要： 学新东西的时候，手上有一个「肯定对」的东西，比什么都让人安心。
5 那循环有什么问题？
对这道题，循环没有任何问题。诚实地讲，这题用循环就够了。
但请看纸上那六行 —— 它描述的是「12345 的答案依赖 1234 的答案」这样一种关系。
循环没有表达这个关系，它是把过程「压平」了：拿一个变量 sum 一路累加，
你得在脑子里模拟指针怎么移动、sum 怎么变化，才能确认它是对的。
这个差别在这道题上无关紧要。但等到问题变成：
- 「一个
n位数的全排列」—— 你得套n重循环，可n是运行时才知道的（第 3 章） - 「从这个格子出发能走到哪些格子」—— 走到新格子后，又要从新格子继续走（第 13 章）
- 「从 (i,j) 走到底的最大和」—— 依赖「从 (i+1,j) 走到底的最大和」（第 17 章）
这些问题的结构本身就是递归的。硬用循环写，你得自己手动维护一个栈来模拟。 所以学递归不是为了炫技，是因为有一大类问题，不用递归表达就会变得极其别扭。
6 ★ 关键的一步
写递归时，你要把自己当成这个函数的使用者，而不是执行者。
写 digitSum(n / 10) 这一行的时候，不要去追问「那它进去之后又会怎么跑」——
一旦开始追问，你的脑子就会陷进无限套娃里，然后卡住。这就是绝大多数人学不会递归的地方，
不是笨，是追问的方向错了。
正确的姿势是：digitSum 这个函数我已经定义好了，它的职责是「返回参数的数位和」。
既然如此，digitSum(1234) 当然返回 1234 的数位和。我直接拿来用就行了。
一句话：先说清楚这个函数负责什么，然后就信任它。
这个信任怎么才不会变成空头支票？靠三件事，缺一不可：
| 要素 | 在这道题里 | 不写会怎样 |
|---|---|---|
| 1. 函数的职责 | digitSum(n) 返回 n 的各位数字之和 | 你自己都说不清它干什么，那就不可能写对 |
| 2. 边界（出口） | n == 0 时返回 0 | 永远递不到底，栈溢出崩溃 |
| 3. 递推关系 | n % 10 + digitSum(n / 10) | 无法把问题变小，同样递不到底 |
第 3 条还藏着一个容易被忽略的要求：递推必须朝着边界走。
这里每次 n / 10 都让 n 严格变小，所以迟早会撞上 n == 0。
如果你写成 digitSum(n) 调用 digitSum(n)，三要素齐了也照样死。
7 递归写法
点「运行 ▶」看结果
就两行。对照上面那张表看：if (n == 0) return 0; 是边界，
return n % 10 + digitSum(n / 10); 是递推关系，函数名和注释说明了职责。
8 看见它是怎么跑的
递归最大的障碍是「看不见」。所以我们在进入和返回的地方各加一行打印，用缩进表示层数。
点「运行 ▶」看结果
跑完之后，请特别注意输出的后半段：
1 + 0 = 1
2 + 1 = 3
3 + 3 = 6
4 + 6 = 10
5 + 10 = 15答案 15 不是在「递下去」的时候算出来的，而是在**「归回来」的路上一层层攒出来的**。 递的时候每一层都只是把问题往下抛，什么都没算；真正的计算发生在返回途中。
在递归函数的开头和结尾各打印一行，用一个全局 depth 变量控制缩进。
以后写 DFS、写记忆化搜索卡住了，这一招永远有效 —— 它能把「看不见的执行过程」变成一张能读的表。
9 单步看调用栈
打印还是太快了。下面这个动画把每一步拆开，你可以停在任何一帧反复看。
看的时候盯住两件事：
- 「递」的阶段：栈越堆越高，每一层都卡在半路，等着下面的结果 —— 没有任何一层算完了。
- 「归」的阶段：栈一层层塌下去，每弹出一层就产出一个值，交给上一层。
栈的高度就是递归深度。每一层都要占用真实的内存（保存参数、局部变量、返回地址）。 默认栈空间通常是 8MB，所以递归深度到几十万层就可能爆栈（程序直接崩溃，不报错）。
数位和最多递归 10 层左右，完全没问题。但第 13 章的 DFS 在大网格上能递归几万层 —— 到时候我们会再回来算这笔账。
10 ★ 对拍：证明你写的递归是对的
现在到了这个站点最有价值的部分。
你已经有一份肯定正确的循环版。那就让它当标准答案：随机造一堆数字， 两份程序各跑一遍，比对结果。只要有一轮对不上，就把那组数据摆出来。
不要直接点「开始对拍」验证我给的代码 —— 那当然是对的，没有意义。
把「递归版」那一栏里的代码整个删掉，换成你自己默写的那份，然后再点开始。 这才是它存在的理由：你不用问任何人，就能知道自己写对没有。
试试故意写错，感受一下它有多灵：
- 把出口改成
if (n == 1) return 1;—— 看它在什么数据上翻车（提示：想想n = 0） - 把递推改成
n / 10 + digitSum(n % 10)（两个操作符写反了） - 干脆把出口整行删掉 —— 会得到「超时」，那其实是栈溢出
对拍只能证明「在生成器造得出的数据范围内没问题」。 如果生成器造的数据太温柔，错误代码照样能蒙混过关。
这不是假设 —— 我在准备第 14 章 BFS 时就踩了这个坑： 一份「漏掉了向上这个方向」的错误代码，在小而空旷的迷宫上连过 500 轮， 把墙加密、网格放大之后，第 55 轮就露馅了。
所以：造数据要往极端里造。多造边界（0、1、最大值）、多造特殊形状。 这件事本身就是一项要练的本事，后面每一章都会再练一次。
11 自测
- 洛谷 P1028 数的计算 —— NOIP2001。递归入门第一题，先想清楚「函数负责什么」
- 洛谷 P5461 赦免战俘 —— 递归分治，能把递归「画」出来，很直观
- 洛谷 P1255 数楼梯 —— 斐波那契。会 TLE —— 别急着优化，记住这个感觉，第 17 章解决它
- 洛谷 P1044 栈 —— 进阶。想不出来就先跳过，学完第 17 章再回来
第 2 章会用汉诺塔把「信任那个还没写完的函数」这件事再练一遍 —— 汉诺塔的递归只有三行，但几乎没人能靠「在脑子里模拟执行」想明白它。 它会逼着你必须用「使用者视角」，是检验这一章有没有真学会的试金石。