文章目录
- 按调用“路数”分（最常见）
- 按“谁调用谁”分
- 按“调用的位置”分（性能优化向）
- 总结
递归是编程语言中常见的算法技巧，但是递归名称很多，我整理了一下递归常见的三种分类法。
按调用“路数”分（最常见）
这是根据一个函数在递归时，会派生出几个“分身”来分类的。
A. 线性递归 (Linear Recursion)
- 特点：函数在递归阶段，只调用一次自己。
- 长相：
voidlinear(int n){if(n<=0)return;// 只调用一次自己linear(n-1);}- 理解：这就像是一个单向链表，或者一根绳子，一头拉着一头，直到拉断（触底反弹）。
- 例子：计算阶乘、遍历单链表。
- 优化：这种递归可以直接改成循环！
B. 树形递归 (Tree Recursion)
*特点：函数在递归阶段，调用了多次（通常是两次或以上）自己。
*长相：
voidtree(int n){if(n<=1)return;// 调用两次自己，这就分叉了！tree(n-1);tree(n-2);}- 理解：这就像是二叉树的遍历，每走一步就分两叉，呈指数级爆炸增长。
- 例子：斐波那契数列（朴素写法）、二叉树遍历。
- 优化：这种递归有两种优化方案，使用显式栈（避免系统栈溢出）和记忆化搜索（加缓存）。但是要视情况而定：显式栈代码复杂；而多线程环境里的fork/join用的树形递归往往是拆分数据集，几乎没有重复的入参，加缓存没有用。
按“谁调用谁”分
这是根据函数调用的“人际关系”来分类的。
A. 直接递归 (Direct Recursion)
- 特点：函数A直接调用自己(A)。
- 长相：
voidA(){// ...A();// 我直接call我自己}- 备注：这是我们最最常用的递归方式。
B. 间接递归 (Indirect Recursion)
- 特点：函数A调用函数B，函数B又反过来调用函数A。
- 长相：
voidA(){// ...B();// 我让兄弟帮我干}voidB(){// ...A();// 兄弟又把活扔回给我}- 理解：这就像是两个人互相踢皮球，直到把球踢烂（栈溢出）或者达成条件停止。
按“调用的位置”分（性能优化向）
这是你提到的尾递归所在的分类，也是性能优化的关键。
A. 头递归 (Head Recursion)
- 特点：先递归调用，拿到结果后，再进行计算（或者说，递归调用在函数体的前面）。
- 长相：
inthead(int n){if(n==0)return0;// 先递归下去，等回来之后，还要做 +n 的操作returnhead(n-1)+n;}- 缺点：必须把每一层的现场（比如这里的 n）都保存在栈里，等着“归”的时候用。容易栈溢出。
B. 尾递归 (Tail Recursion) —— 你提到的那位
- 特点：递归调用是函数的最后一步操作。调用之后，函数不需要再做任何计算了，直接返回结果就行。
- 长相：
inttail(int n,int acc){if(n==0)returnacc;// 计算已经在参数里做完了(acc + n)，这里只是单纯的跳转returntail(n-1,acc+n);}- 优点：编译器可以进行尾调用优化 (TCO)。它不需要保留上一层的栈帧，直接把当前栈覆盖掉就行。这样，无论递归多少层，栈空间永远是 O(1) 的，不会栈溢出。
总结
| 分类维度 | 类型 | 关键特征 |
|---|---|---|
| 调用路数 | 线性递归 | 一层只调一次自己 |
| 树形递归 | 一层调多次自己 | |
| 调用关系 | 直接递归 | 自己调自己 |
| 间接递归 | 你调我，我调你 | |
| 调用位置 | 头递归 | 调完还要算 |
| 尾递归 | 调完直接返 |
