安顺市网站建设_网站建设公司_自助建站_seo优化

递归是编程语言中常见的算法技巧，但是递归名称很多，我整理了一下递归常见的三种分类法。

按调用“路数”分（最常见）

这是根据一个函数在递归时，会派生出几个“分身”来分类的。

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) 的，不会栈溢出。

总结

分类维度	类型	关键特征
调用路数	线性递归	一层只调一次自己
树形递归	一层调多次自己
调用关系	直接递归	自己调自己
间接递归	你调我，我调你
调用位置	头递归	调完还要算
尾递归	调完直接返