目录
尾递归（Tail Recursion）
尾递归是递归函数的一种特殊形式：
一个函数在递归调用之后，不再做任何额外的操作，而是“直接返回”这个递归调用的结果。
也就是说，递归调用是函数中的最后一步，没有其他计算或操作跟在它后面。
void fun(int x)
{
if(x > 0)
{
printf("%d", x);
fun(x - 1);
}
}
分析：
printf("%d", x);是当前函数的最后一个非递归操作。fun(x - 1);是函数体中最后一个执行的动作，它后面没有其它操作。调用的返回值也没有被用在任何表达式中，比如赋值、加法等。
✅所以这是尾递归。
在尾递归中，当前函数的调用栈帧不需要保存，因为没有额外操作依赖返回值，编译器甚至可以优化为循环（loop），提高效率。
void fun(int n)
{
if(n > 0)
{
printf("%d", n);
fun(n - 1) + n;
}
}
分析：
这里虽然
fun(n - 1)是递归调用，但它不是函数体中的最后操作。还有一个
+ n—— 表示你需要获取fun(n - 1)的返回值后，再与n相加。这意味着 当前栈帧必须保留，等待子调用返回后进行加法操作。
❌ 所以这不是尾递归。
什么是 Loop（循环）？
Loop（循环） 是程序中一种重复执行代码的结构。
常见的 C++ 循环有：
for循环：已知循环次数while循环：满足条件就循环do...while：至少执行一次
将递归转化为 循环
void fun_loop(int x)
{
while(x > 0)
{
printf("%d", x);
x--;
}
}
转化步骤说明：
把
x看作循环变量；fun(x - 1);→x--;把
if (x > 0)→ 变成while(x > 0);保持
printf逻辑不变；
🎯 核心联系：
所有尾递归都可以被转换为循环（Loop）；
但非尾递归不一定能直接转换为 Loop（可能需要用栈模拟）。
复杂度分析
时间复杂度分析
无论是递归版本还是循环版本，printf 一次就是常数时间 O(1)，每次都打印一个数字。
递归版本：
当
x = n时，会调用fun(n), fun(n-1), ..., fun(1)，共n次。每次调用只做一次
printf，没有重复计算。
✅ 时间复杂度：O(n)
循环版本：
同样执行 n 次 printf，逻辑完全等价于递归。
✅ 时间复杂度：O(n)
空间复杂度分析
递归版本：
每一次函数调用，都会占用一层调用栈帧。
所以
fun(5)会占用 5 层栈空间。栈大小是受语言/平台限制的，过多递归可能导致 栈溢出（stack overflow）。
❌ 空间复杂度：O(n)（用于递归栈）
循环版本：
不存在函数嵌套调用，变量
x是一个普通变量。不会占用额外栈帧。
✅ 空间复杂度：O(1)（常量空间）
头递归（Head Recursion）
头递归（Head Recursion） 是指：
函数中 先调用自己，再执行其他操作 的递归形式。
💡 特点：
函数体中，递归调用在最前面。
所有的动作都发生在“返回之后”。
结构上与“尾递归”相反，先深入到底，再回溯处理”。
void fun(int n)
{
if(n > 0)
{
fun(n - 1);
printf("%d", n);
}
}
调用流程：
fun(3)
└── fun(2)
└── fun(1)
└── fun(0) → 终止
然后开始回溯：
尾递归：打印从 3 → 2 → 1（调用时就执行）
头递归：打印从 1 → 2 → 3（回溯时执行）
将头递归转换为循环
void fun(int n)
{
int i = 1;
while(i<=n)
{
printf("%d",i);
i++;
}
}
树形递归（Tree Recursion）
树形递归是指函数在每次调用时，会递归地调用自己 两次或更多次，从而形成一个“树状”结构的调用图。
📌 特征：
每个递归分支会继续递归产生更多子分支。
递归调用数量呈指数级增长。
典型例子是斐波那契数列、全排列、子集生成、分治算法等。
线性递归（Linear Recursion）
线性递归是指函数在每次调用时，只进行一次递归调用，然后再进行其他操作。
📌 特征：
递归过程是一条“直线”，只有一条路径向下。
每一层只调用下一层一次。
常见于计数、求和、遍历等线性结构。
void fun(int n)
{
if(n > 0)
{
printf("%d", n);
fun(n - 1);
fun(n - 1);
}
}
递归调用树（fun(3)）
fun(3)
/ \
printf(3) printf(3)
fun(2) fun(2)
/ \ / \
printf(2) printf(2) printf(2) printf(2)
fun(1) fun(1) fun(1) fun(1)
/ \ / \ / \ / \
printf(1) printf(1) ... ... ... ... ... ...
fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0)
fun(3)
/ \
fun(2) fun(2)
/ \ / \
fun(1) fun(1) fun(1) fun(1)
/ \ / \ / \ / \
fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0) fun(0)
每个 fun(n) 节点都对应一次：printf(n)
栈帧变化
我们使用“压栈（调用）”和“弹栈（返回）”来标记栈帧变化。
⬇️ 调用开始：main() → fun(3)
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
打印：3
⬇️ fun(3) 调用 fun(2)：
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
打印：2
⬇️ fun(2) 调用 fun(1)：
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
打印：1
⬇️ fun(1) 调用 fun(0)
+------------------------+
| fun(n=0) 的栈帧 |
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
n == 0，返回，弹出 fun(0) 栈帧：
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
⬇️ fun(1) 再调用第二个 fun(0)
+------------------------+
| fun(n=0) 的栈帧 |
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
返回，弹出 fun(0)：
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
fun(1) 完成，弹出：
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
⬇️ fun(2) 现在调用第二个 fun(1)（结构一样）
⬇️ fun(3) 现在调用第二个 fun(2)
调用 fun(2) → fun(1) → fun(0) → fun(0) → 返回
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
进入 fun(1)，打印 1，两次 fun(0)，弹栈
再次 fun(1)，打印 1，两次 fun(0)，弹栈
完成所有调用，弹出所有栈帧。
最终输出顺序：3 2 1 1 2 1 1
复杂度分析
时间复杂度分析：递归调用树逐层计数
调用树节点数量（按层）
| 层数（Level） | 调用的是 fun(x) | 节点个数 |
|---|---|---|
| 第 0 层 | fun(3) | 1 |
| 第 1 层 | fun(2) | 2 |
| 第 2 层 | fun(1) | 4 |
| 第 3 层 | fun(0) | 8（终止） |
总调用次数 = 每个 fun(n) 的数量 = 1 + 2 + 4 + 8 = 15
这是一个 等比数列求和：
当 n = 3 时：
T(3)=2^4−1=15
当 n 变大时，忽略常数与低阶项：时间复杂度：T(n) = O(2^n)
空间复杂度分析：根据栈深度（调用路径）分析
空间复杂度 = 递归过程中 最大栈帧深度
一个分支调用路径是：
fun(3)
→ fun(2)
→ fun(1)
→ fun(0)
每次递归调用先执行第一个子调用，然后第二个
每个调用都等第二个调用结束后才能返回
所以是深度优先的栈式调用
最大栈帧数 = 调用最长的一条路径
+------------------------+
| fun(n=0) 的栈帧 |
+------------------------+
| fun(n=1) 的栈帧 |
+------------------------+
| fun(n=2) 的栈帧 |
+------------------------+
| fun(n=3) 的栈帧 |
+------------------------+
| main() 的栈帧 |
+------------------------+
共计 4 层栈帧
空间复杂度结论：
空间复杂度 = 最大栈帧数 = O(n)
（这里 n 是初始的 fun(n) 的值）
间接递归（Indirect Recursion）
间接递归是指：函数 A 调用函数 B，函数 B 又调用函数 A，形成“循环调用”结构，但自己不直接调用自己。
📌 特征：
A → B → A → B → … 互相递归
没有函数直接调用自己，但仍然形成递归链
本质上仍然需要使用函数栈，类似直接递归的行为
void funA(int n)
{
if(n > 0)
{
printf("%d", n);
funB(n - 1);
}
}
void funB(int x)
{
if(x > 0)
{
printf("%d", x);
funA(x / 2);
}
}
递归调用树
funA(3)
/ \
printf(3) funB(2)
/ \
printf(2) funA(1)
/ \
printf(1) funB(0)
复杂度分析
✅时间复杂度
是否能泛化为 n 的函数？
我们发现：
每次 funA(n) → funB(n-1)
每次 funB(x) → funA(x/2)
所以这是一个交错型链式调用。
建函数调用深度模型（从 n=3 推到 n）
设：
A 调用 B(n-1)
B 调用 A(n/2)
构成链状结构：
A(n) → B(n-1) → A((n-1)/2) → B((n-1)/2 - 1) → ...
n → n-1 → ⌊(n-1)/2⌋ → ⌊(n-1)/2⌋ - 1 → ...
这是一个交替递减+对数递减的组合过程。
下降几次会结束？
这是一个类似：
n→n−1→⌊2n−1⌋→⌊2n−1⌋−1→...
混合了 线性减1 和 对数除2 的过程
最多不会超过：
线性下降：O(n)
对数下降：O(log n)
所以 时间复杂度：O(log n + n) = O(n)（近似线性）
✅空间复杂度（最大栈帧）
因为调用是链状交替（A→B→A→B...），所以 最大调用深度 就是这条链的长度。
最多有 O(n) 次连续调用 → 最大栈深度为 O(n)
嵌套递归（Nested Recursion）
嵌套递归是指：递归调用的参数本身又是一个递归调用。
也就是：
fun(fun(n + 11))
它的核心区别是：
递归调用不是
fun(n - 1)这种简单线性变化；而是 “求出 fun(n+11) 的结果，然后再用它作为参数再次调用
fun”。
int fun(int n)
{
if(n > 100)
{
return n - 10;
}
else
{
return fun(fun(n + 11));
}
}
递归调用树
fun(95)
/ \
fun(106) = 96 fun(96)
/ \
fun(107) = 97 fun(97)
/ \
fun(108) = 98 fun(98)
/ \
fun(109) = 99 fun(99)
fun(99)
/ \
fun(110) = 100 fun(100)
/ \
fun(111) = 101 fun(101)
↓
base case
最终回溯后 fun(95) 会返回 91
