数据结构：递归的种类（Types of Recursion）

目录

尾递归（Tail Recursion）

什么是 Loop（循环）？

 复杂度分析

 头递归（Head Recursion）

 树形递归（Tree Recursion）

线性递归（Linear Recursion）

递归调用树（fun(3)）

栈帧变化

复杂度分析

 间接递归（Indirect Recursion）

复杂度分析 

嵌套递归（Nested Recursion）

递归调用树 

---

尾递归（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--;}
}

转化步骤说明：

1. 把 x 看作循环变量；

2. fun(x - 1); → x--;

3. 把 if (x > 0) → 变成 while(x > 0);

4. 保持 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