【递归入门】---- 识别递归问题 + 三步写出正确代码

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. 避坑指南

口诀：
“先写出口，再缩问题，相信子问题能搞定。”

5. 总结

• 适合递归的问题 = 自相似 + 有出口 + 能缩小
• 写递归的三步心法：
  1️⃣ 写基线条件（先保命）
  2️⃣ 定义递归关系（信子问题）
  3️⃣ 实现缩小工具（辅助逻辑）
• 不要怕递归——它只是“让问题自己解决自己”的思维方式。