1. 题目描述：求“数根”问题
题目链接
给定正整数n nn（如 38），不断将其各位数字相加，直到结果为一位数。
38 → 3+8=11 → 1+1=2 → 输出 2这道题可用循环轻松解决，但我们的目标是：用递归来写，并从中提炼通用方法。
2. 什么样的问题适合用递归？
不是所有问题都值得用递归。真正适合递归的问题，通常具备以下三个特征：
特征 1：自相似性（Self-similarity）
问题的结构在不同规模下“看起来一样”。
数根：
f(n) = f(各位和)→ 问题形式完全相同阶乘：
n! = n × (n-1)!
一句话判断：
如果你能用“……的……”来描述问题（如 n 的数根 =（n 的各位数字之和）的数根。），那它很可能适合递归。
特征 2：存在明确的最小情况（Base Case）
必须有无需递归就能直接回答的情形。
- 数根：
n < 10→ 直接返回n - 阶乘：
0! = 1
没有基线条件 → 无限递归 → 栈溢出！
特征 3：每次递归让问题变小并趋近基线
参数必须朝着终止条件收敛。
n → sum_of_digits(n)（38 → 11 → 2）n → n-1（阶乘）
❌ 如果递归后问题没变小（如f(n) = f(n)），就会死循环。
3. 如何写出正确的递归程序？——三步心法
掌握了“识别”，接下来是“构造”。我们用递归三步心法来写“数根”：
第一步：写出基线条件（Base Case）
问：什么情况下，我不需要再递归？
对数根：
→ 如果n < 10，它本身就是答案！
if(n<10){returnn;// 出口！}技巧：先写这一行，避免忘记出口。
第二步：定义递归关系（Recursive Step）
问：当前问题能否转化为一个“更小”的同类问题？
对数根：
→ 先算各位和x，然后求x的数根！
returncalc(x);// 问题规模缩小关键心态：
不要试图脑内展开所有调用！
只需相信：calc(x)能正确返回x的数根。你只负责当前层。
第三步：实现“缩小问题”的工具
有时需要一小段逻辑生成子问题输入。
对数根：计算各位和：
intx=0;while(n){x+=n%10;n/=10;}这段代码不属于递归思想本身，只是辅助。可内联，也可拆成独立函数。
完整代码：三步合一
#include<bits/stdc++.h>usingnamespacestd;intcalc(intn){// 第一步：基线条件if(n<10)returnn;// 第三步：工具——计算各位和intx=0;while(n){x+=n%10;n/=10;}// 第二步：递归调用（问题变小）returncalc(x);}intmain(){intn;cin>>n;cout<<calc(n)<<endl;return0;}安全（递归深度 ≤ 3）
正确（符合数学定义）
清晰（三步结构分明）
4. 避坑指南
| 错误 | 表现 | 解决方案 |
|---|---|---|
| 忘记基线条件 | 栈溢出 | 先写if (base) return ... |
| 问题没变小 | 无限递归 | 检查参数是否真的缩小（如n → x < n） |
| 过度复杂化 | 逻辑混乱 | 只专注当前层：判断 → 缩小 → 调用 |
口诀：
“先写出口，再缩问题，相信子问题能搞定。”
5. 总结
- 适合递归的问题 = 自相似 + 有出口 + 能缩小
- 写递归的三步心法：
1️⃣ 写基线条件（先保命）
2️⃣ 定义递归关系（信子问题）
3️⃣ 实现缩小工具（辅助逻辑） - 不要怕递归——它只是“让问题自己解决自己”的思维方式。
