文章目录
深入理解递归：从函数调用到调用栈的完整执行过程
前言
一、什么是递归
二、阶乘的递归定义
三、源代码只有一个调用位置，为什么会调用很多次
四、函数代码只有一份，调用状态可以有很多份
[五、每一层中的参数 `n` 为什么不会互相覆盖](#五、每一层中的参数 n 为什么不会互相覆盖)
六、什么是函数调用栈
七、什么是栈帧
八、什么是返回地址
[九、`return n * factorial(n - 1)` 不是一步完成的](#九、return n * factorial(n - 1) 不是一步完成的)
十、阶乘递归的完整入栈过程
[1. 进入 `factorial(6)`](#1. 进入 factorial(6))
[2. 进入 `factorial(5)`](#2. 进入 factorial(5))
[3. 进入 `factorial(4)`](#3. 进入 factorial(4))
[4. 进入 `factorial(3)`](#4. 进入 factorial(3))
[5. 进入 `factorial(2)`](#5. 进入 factorial(2))
[6. 进入 `factorial(1)`](#6. 进入 factorial(1))
十一、递归终止条件如何停止继续调用
十二、阶乘递归的完整出栈过程
[1. 恢复 `factorial(2)`](#1. 恢复 factorial(2))
[2. 恢复 `factorial(3)`](#2. 恢复 factorial(3))
[3. 恢复 `factorial(4)`](#3. 恢复 factorial(4))
[4. 恢复 `factorial(5)`](#4. 恢复 factorial(5))
[5. 恢复 `factorial(6)`](#5. 恢复 factorial(6))
十三、递归为什么符合后进先出
十四、递归中的暂停与恢复
十五、递归不会自动创建多个线程
[十六、代码中为什么没有手动写 `push` 和 `pop`](#十六、代码中为什么没有手动写 push 和 pop)
十七、从汇编角度理解函数调用
十八、CPU如何回到上一层函数
十九、通过局部变量地址观察递归层次
二十、使用显式栈模拟递归
二十一、递归也可以改写成循环
二十二、递归、显式栈和循环的区别
二十三、为什么树结构适合递归
二十四、直接递归与间接递归
[1. 直接递归](#1. 直接递归)
[2. 间接递归](#2. 间接递归)
二十五、递归调用和普通函数调用没有本质区别
二十六、递归深度
二十七、什么是栈溢出
二十八、尾递归
二十九、C++标准是否规定递归必须使用物理栈
[三十、使用 GDB 观察递归调用栈](#三十、使用 GDB 观察递归调用栈)
三十一、完整时序图
三十二、递归函数的基本编写模板
三十三、正确递归的三个必要条件
[1. 必须存在终止条件](#1. 必须存在终止条件)
[2. 每次递归必须缩小问题](#2. 每次递归必须缩小问题)
[3. 当前问题必须依赖子问题结果](#3. 当前问题必须依赖子问题结果)
三十四、常见误区
[1. 认为代码中没有 `std::stack` 就没有使用栈](#1. 认为代码中没有 std::stack 就没有使用栈)
[2. 认为递归会复制多份函数代码](#2. 认为递归会复制多份函数代码)
[3. 认为所有递归层共享同一个参数](#3. 认为所有递归层共享同一个参数)
[4. 认为外层函数已经执行结束](#4. 认为外层函数已经执行结束)
[5. 认为递归函数在并行执行](#5. 认为递归函数在并行执行)
[6. 认为函数返回后所有信息都会丢失](#6. 认为函数返回后所有信息都会丢失)
[7. 忽略整数溢出](#7. 忽略整数溢出)
三十五、安全的阶乘完整代码
三十六、复杂度分析
三十七、递归执行模型总结
三十八、最终结论
深入理解递归：从函数调用到调用栈的完整执行过程
前言
递归是一种函数直接或间接调用自身的程序设计方式。
例如，使用递归计算阶乘：
cpp
复制代码
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
return n * factorial(n - 1);
}
调用：
cpp
复制代码
int result = factorial(6);
从数学关系上，可以展开为：
text
复制代码
factorial(6)
= 6 × factorial(5)
= 6 × 5 × factorial(4)
= 6 × 5 × 4 × factorial(3)
= 6 × 5 × 4 × 3 × factorial(2)
= 6 × 5 × 4 × 3 × 2 × factorial(1)
= 6 × 5 × 4 × 3 × 2 × 1
= 720
真正需要理解的是：
text
复制代码
源代码中只有一条 factorial(n - 1)，
为什么运行时可以连续调用 factorial(5)、factorial(4)、
factorial(3)、factorial(2)、factorial(1)？
同时，代码中没有显式创建 std::stack，也没有手动编写 push() 和 pop()，程序为什么能够记住每一层的参数和返回位置？
核心原因是：
每次函数调用都会产生一份独立的调用状态。主流 C++ 程序通常通过线程调用栈中的栈帧保存这些状态。
递归并不是没有使用栈，而是使用了由编译器、调用约定和处理器共同维护的函数调用栈。
一、什么是递归
当一个函数在执行过程中再次调用自己时，就形成了递归。
例如：
cpp
复制代码
void function()
{
function();
}
调用关系是：
text
复制代码
function()
↓
function()
↓
function()
↓
function()
↓
...
这种写法没有终止条件，会不断调用自身，最终耗尽调用栈空间。
一个正确的递归函数通常包含三个部分：
text
复制代码
1. 递归终止条件；
2. 问题规模缩小；
3. 使用子问题结果解决当前问题。
阶乘函数正好包含这三个部分：
cpp
复制代码
int factorial(int n)
{
// 1. 递归终止条件
if (n <= 1)
{
return 1;
}
// 2. 问题规模由 n 缩小为 n - 1
// 3. 使用 factorial(n - 1) 解决 factorial(n)
return n * factorial(n - 1);
}
二、阶乘的递归定义
正整数阶乘定义为：
text
复制代码
n! = n × (n - 1) × (n - 2) × ... × 2 × 1
例如：
text
复制代码
5! = 5 × 4 × 3 × 2 × 1 = 120
阶乘也可以写成递归关系：
text
复制代码
n! = n × (n - 1)!
终止条件为：
text
复制代码
0! = 1
1! = 1
因此：
text
复制代码
6! = 6 × 5!
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1
对应代码：
cpp
复制代码
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
return n * factorial(n - 1);
}
三、源代码只有一个调用位置，为什么会调用很多次
源代码中确实只写了一条递归调用：
cpp
复制代码
factorial(n - 1);
但是，这条语句会在每一次新的 factorial() 调用中再次执行。
调用：
cpp
复制代码
factorial(6);
第一次进入函数时：
text
复制代码
n = 6
判断：
cpp
复制代码
n <= 1
结果为假，因此执行：
cpp
复制代码
factorial(5);
程序重新进入同一个函数，第二次调用中的参数为：
text
复制代码
n = 5
这一次又会执行：
cpp
复制代码
factorial(4);
第三次进入函数后：
text
复制代码
n = 4
又会执行：
cpp
复制代码
factorial(3);
因此，虽然源代码中只有一个递归调用位置，但该位置会在不同的函数调用中反复执行。
可以区分两个概念：
text
复制代码
静态调用位置：
源代码中一共写了多少个调用表达式。
动态调用次数：
程序运行过程中，这些调用表达式实际执行了多少次。
对于：
cpp
复制代码
factorial(6);
结果是：
text
复制代码
静态递归调用位置：1 个
运行时 factorial 调用次数：6 次
这和循环类似。
例如：
cpp
复制代码
for (int i = 0; i < 5; ++i)
{
print();
}
代码中只写了一次：
cpp
复制代码
print();
但是这条语句会在循环过程中执行五次。
递归不是通过循环回到原语句，而是通过新的函数调用重新执行同一份函数代码。
四、函数代码只有一份，调用状态可以有很多份
假设 factorial() 编译后的机器指令位于代码区：
text
复制代码
0x00401000：factorial 函数机器代码
无论调用：
cpp
复制代码
factorial(6);
factorial(5);
factorial(4);
执行的都是同一份机器指令。
程序不会因为调用了六次函数，就复制六份 factorial() 代码。
可以表示为：
text
复制代码
代码区：
┌─────────────────────────────┐
│ factorial 的机器指令 │
│ 通常只有一份 │
└─────────────────────────────┘
▲
│
多次调用执行同一份代码
│
┌──────────────┼──────────────┐
│ │ │
│ n = 6 │ n = 5 │ n = 4
│ 调用状态 1 │ 调用状态 2 │ 调用状态 3
因此需要区分：
text
复制代码
函数代码：通常只有一份；
函数调用状态：每次调用各有一份。
每次调用拥有独立的：
text
复制代码
参数
局部变量
返回地址
临时计算状态
必要的寄存器状态
五、每一层中的参数 n 为什么不会互相覆盖
虽然每次调用中的参数都叫作 n，但它们属于不同的函数调用。
调用：
cpp
复制代码
factorial(6);
第一次调用中的 n：
text
复制代码
n = 6
该函数继续调用：
cpp
复制代码
factorial(5);
第二次调用拥有自己的参数：
text
复制代码
n = 5
它们不是同一个变量。
概念上可以表示为：
text
复制代码
factorial(6) 的调用状态：
┌─────────────────────────┐
│ 参数 n = 6 │
│ 等待 factorial(5) 返回 │
└─────────────────────────┘
factorial(5) 的调用状态：
┌─────────────────────────┐
│ 参数 n = 5 │
│ 等待 factorial(4) 返回 │
└─────────────────────────┘
继续递归后：
text
复制代码
factorial(4) 拥有自己的 n = 4
factorial(3) 拥有自己的 n = 3
factorial(2) 拥有自己的 n = 2
factorial(1) 拥有自己的 n = 1
每一层使用的是独立的调用状态，所以不会相互覆盖。
六、什么是函数调用栈
程序中的每个线程通常都拥有自己的调用栈。
调用栈用于管理函数调用的进入和返回。
它遵循：
text
复制代码
后进先出
英文称为：
text
复制代码
LIFO：Last In, First Out
当一个函数调用另一个函数时，新的函数调用状态被加入调用栈。
当被调用函数返回时，最上层的调用状态被移除，然后恢复上一层函数。
例如：
cpp
复制代码
int main()
{
int result = factorial(3);
}
调用关系：
text
复制代码
main()
↓
factorial(3)
↓
factorial(2)
↓
factorial(1)
调用栈概念图：
text
复制代码
栈顶
│
▼
┌──────────────────────┐
│ factorial(1) │
├──────────────────────┤
│ factorial(2) │
├──────────────────────┤
│ factorial(3) │
├──────────────────────┤
│ main() │
└──────────────────────┘
返回时顺序相反：
text
复制代码
factorial(1) 最先返回
factorial(2) 随后返回
factorial(3) 再返回
main() 最后继续执行
七、什么是栈帧
每一次函数调用对应的调用记录通常称为：
text
复制代码
栈帧
英文名称：
text
复制代码
Stack Frame
一个栈帧可能保存：
text
复制代码
函数参数
局部变量
返回地址
临时计算结果
被调用者需要恢复的寄存器
栈帧管理信息
概念结构：
text
复制代码
┌─────────────────────────────┐
│ 函数参数 │
├─────────────────────────────┤
│ 局部变量 │
├─────────────────────────────┤
│ 临时计算数据 │
├─────────────────────────────┤
│ 保存的寄存器 │
├─────────────────────────────┤
│ 函数返回地址 │
└─────────────────────────────┘
实际实现会因以下因素而变化：
text
复制代码
处理器架构
操作系统
编译器
优化等级
ABI
函数调用约定
现代处理器通常会优先使用寄存器传递部分参数，编译器也可能把局部变量保存在寄存器中。
因此，不能简单认为所有数据都一定物理存放在栈内存里。
更准确的说法是：
每次函数调用都必须拥有独立的调用状态；在主流实现中，这些状态通常由调用栈、寄存器及相关调用约定共同维护。
八、什么是返回地址
函数调用完成后，程序必须知道应该回到哪里继续执行。
例如：
cpp
复制代码
int result = factorial(6);
std::cout << result << '\n';
当 factorial(6) 执行结束后，程序需要回到：
cpp
复制代码
std::cout << result << '\n';
之前继续执行。
这个位置对应的机器指令地址称为：
text
复制代码
返回地址
递归调用也是一样。
执行：
cpp
复制代码
return n * factorial(n - 1);
当前层调用 factorial(n - 1) 之前，必须记住：
text
复制代码
子函数返回后，
还要使用当前层的 n 与子函数返回值相乘。
例如 factorial(6) 需要记住：
text
复制代码
factorial(5) 返回以后，
需要计算 6 × factorial(5) 的返回值。
这份"接下来从哪里继续执行"的信息，是函数能够正确返回上一层的关键。
九、return n * factorial(n - 1) 不是一步完成的
下面这行代码：
cpp
复制代码
return n * factorial(n - 1);
从逻辑上至少包含以下步骤：
text
复制代码
1. 保存当前调用中的 n；
2. 计算参数 n - 1；
3. 调用 factorial(n - 1)；
4. 等待子调用返回；
5. 获取子调用返回值；
6. 用当前层的 n 乘以返回值；
7. 返回最终乘积。
可以将代码展开为：
cpp
复制代码
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
int childResult = factorial(n - 1);
int result = n * childResult;
return result;
}
当执行到：
cpp
复制代码
int childResult = factorial(n - 1);
当前函数不能继续执行后面的乘法。
它必须等待子函数返回。
等待期间，当前函数的：
text
复制代码
参数 n
返回位置
后续计算任务
必须被保存。
这正是函数调用状态存在的意义。
十、阶乘递归的完整入栈过程
调用：
cpp
复制代码
factorial(6);
1. 进入 factorial(6)
当前调用状态：
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(6) │
│ n = 6 │
└───────────────────────────┘
由于：
text
复制代码
6 > 1
需要计算：
text
复制代码
6 × factorial(5)
factorial(5) 尚未得到结果，所以当前调用暂停，进入下一层。
2. 进入 factorial(5)
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(5) │
│ n = 5 │
├───────────────────────────┤
│ factorial(6) │
│ n = 6 │
│ 等待：6 × 子调用返回值 │
└───────────────────────────┘
factorial(5) 又需要计算：
text
复制代码
5 × factorial(4)
于是继续调用下一层。
3. 进入 factorial(4)
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(4) │
│ n = 4 │
├───────────────────────────┤
│ factorial(5) │
│ n = 5 │
│ 等待：5 × 子调用返回值 │
├───────────────────────────┤
│ factorial(6) │
│ n = 6 │
│ 等待：6 × 子调用返回值 │
└───────────────────────────┘
4. 进入 factorial(3)
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(3) │
│ n = 3 │
├───────────────────────────┤
│ factorial(4) │
│ n = 4 │
│ 等待：4 × 子调用返回值 │
├───────────────────────────┤
│ factorial(5) │
│ n = 5 │
│ 等待：5 × 子调用返回值 │
├───────────────────────────┤
│ factorial(6) │
│ n = 6 │
│ 等待：6 × 子调用返回值 │
└───────────────────────────┘
5. 进入 factorial(2)
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(2) │
│ n = 2 │
├───────────────────────────┤
│ factorial(3) │
│ n = 3 │
│ 等待：3 × 子调用返回值 │
├───────────────────────────┤
│ factorial(4) │
│ n = 4 │
│ 等待：4 × 子调用返回值 │
├───────────────────────────┤
│ factorial(5) │
│ n = 5 │
│ 等待：5 × 子调用返回值 │
├───────────────────────────┤
│ factorial(6) │
│ n = 6 │
│ 等待：6 × 子调用返回值 │
└───────────────────────────┘
6. 进入 factorial(1)
text
复制代码
栈顶
│
▼
┌───────────────────────────┐
│ factorial(1) │
│ n = 1 │
├───────────────────────────┤
│ factorial(2) │
│ n = 2 │
│ 等待：2 × 子调用返回值 │
├───────────────────────────┤
│ factorial(3) │
│ n = 3 │
│ 等待：3 × 子调用返回值 │
├───────────────────────────┤
│ factorial(4) │
│ n = 4 │
│ 等待：4 × 子调用返回值 │
├───────────────────────────┤
│ factorial(5) │
│ n = 5 │
│ 等待：5 × 子调用返回值 │
├───────────────────────────┤
│ factorial(6) │
│ n = 6 │
│ 等待：6 × 子调用返回值 │
└───────────────────────────┘
这就是递归中的"递"。
每进入一层，就产生一个新的调用状态。
十一、递归终止条件如何停止继续调用
函数中存在：
cpp
复制代码
if (n <= 1)
{
return 1;
}
当进入：
text
复制代码
factorial(1)
时：
text
复制代码
n <= 1
条件成立，函数直接返回：
cpp
复制代码
return 1;
不会再执行：
cpp
复制代码
factorial(n - 1);
因此递归停止继续深入。
终止条件也称为：
text
复制代码
递归基
基础情况
Base Case
如果没有终止条件：
cpp
复制代码
int factorial(int n)
{
return n * factorial(n - 1);
}
调用过程将不断继续：
text
复制代码
factorial(6)
factorial(5)
factorial(4)
...
factorial(0)
factorial(-1)
factorial(-2)
...
调用栈会不断增长，最终可能产生栈溢出。
十二、阶乘递归的完整出栈过程
进入 factorial(1) 后，终止条件返回：
text
复制代码
factorial(1) = 1
最上层调用状态结束，控制权回到 factorial(2)。
1. 恢复 factorial(2)
原本等待的计算：
text
复制代码
2 × factorial(1)
现在已经得到：
text
复制代码
factorial(1) = 1
因此：
text
复制代码
factorial(2)
= 2 × 1
= 2
factorial(2) 返回 2。
2. 恢复 factorial(3)
text
复制代码
factorial(3)
= 3 × factorial(2)
= 3 × 2
= 6
返回 6。
3. 恢复 factorial(4)
text
复制代码
factorial(4)
= 4 × factorial(3)
= 4 × 6
= 24
返回 24。
4. 恢复 factorial(5)
text
复制代码
factorial(5)
= 5 × factorial(4)
= 5 × 24
= 120
返回 120。
5. 恢复 factorial(6)
text
复制代码
factorial(6)
= 6 × factorial(5)
= 6 × 120
= 720
最终返回：
text
复制代码
720
整个回归过程：
text
复制代码
factorial(1) 返回 1
│
▼
factorial(2) 返回 2
│
▼
factorial(3) 返回 6
│
▼
factorial(4) 返回 24
│
▼
factorial(5) 返回 120
│
▼
factorial(6) 返回 720
这就是递归中的"归"。
十三、递归为什么符合后进先出
函数进入顺序：
text
复制代码
factorial(6)
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
函数返回顺序：
text
复制代码
factorial(1)
factorial(2)
factorial(3)
factorial(4)
factorial(5)
factorial(6)
最后进入的 factorial(1) 最先返回。
最先进入的 factorial(6) 最后返回。
这正好符合栈的规则：
text
复制代码
后进先出
因此调用栈非常适合管理嵌套函数调用。
十四、递归中的暂停与恢复
递归过程中，外层函数并没有执行结束，而是暂时停在调用子函数的位置。
例如：
cpp
复制代码
int childResult = factorial(n - 1);
int result = n * childResult;
执行 factorial(6) 时：
text
复制代码
factorial(6) 暂停，等待 factorial(5)
factorial(5) 暂停，等待 factorial(4)
factorial(4) 暂停，等待 factorial(3)
factorial(3) 暂停，等待 factorial(2)
factorial(2) 暂停，等待 factorial(1)
到达终止条件后：
text
复制代码
factorial(1) 返回
factorial(2) 恢复
factorial(2) 返回
factorial(3) 恢复
...
这里的暂停不表示创建了新的线程。
普通递归仍然在同一个线程中顺序执行。
更准确地说：
外层调用尚未完成，其执行上下文被保存；控制流进入更深一层调用，子调用返回后再恢复外层上下文。
十五、递归不会自动创建多个线程
普通递归：
cpp
复制代码
factorial(6);
通常只有一个线程执行。
调用关系虽然有很多层：
text
复制代码
factorial(6)
└── factorial(5)
└── factorial(4)
└── factorial(3)
└── factorial(2)
└── factorial(1)
但同一时刻只有最内层尚未暂停的函数在继续执行。
递归产生的是：
text
复制代码
多个函数调用状态
而不是：
text
复制代码
多个并发线程
只有程序显式创建线程时，才会形成真正的并发执行。
十六、代码中为什么没有手动写 push 和 pop
std::stack 是程序员可以显式使用的标准库容器适配器。
函数调用栈则属于程序运行时的调用机制。
二者不是同一个东西。
text
复制代码
std::stack：
程序员在业务代码中主动创建和操作的数据结构。
函数调用栈：
程序运行函数调用时使用的执行机制。
当源代码写下：
cpp
复制代码
factorial(n - 1);
编译器会生成函数调用所需的机器指令。
调用过程通常需要完成：
text
复制代码
准备函数参数
保存返回位置
保存必要寄存器
为新的调用准备空间
跳转到函数入口
函数返回时通常需要：
text
复制代码
恢复必要寄存器
恢复栈指针
取得返回地址
跳回调用者
这些操作由：
text
复制代码
编译器
处理器指令
平台 ABI
函数调用约定
调用栈
共同完成。
所以 C++ 源代码中不需要手动写：
cpp
复制代码
callStack.push(...);
callStack.pop();
十七、从汇编角度理解函数调用
下面是一段用于解释原理的简化伪汇编。
C++ 代码：
cpp
复制代码
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
return n * factorial(n - 1);
}
在未优化情况下，可能产生类似结构：
asm
复制代码
factorial:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp - 4], edi
cmp DWORD PTR [rbp - 4], 1
jg recursive_case
mov eax, 1
leave
ret
recursive_case:
mov eax, DWORD PTR [rbp - 4]
sub eax, 1
mov edi, eax
call factorial
imul eax, DWORD PTR [rbp - 4]
leave
ret
真实汇编会受平台、编译器和优化等级影响，上面只用于说明调用流程。
最关键的指令是：
asm
复制代码
call factorial
它会发起一次新的函数调用。
函数执行结束时：
asm
复制代码
ret
会根据保存的返回地址回到调用者。
第一次执行 call factorial 时：
text
复制代码
当前 n = 6
调用 factorial(5)
第二次进入函数后，程序又运行到相同的调用指令：
text
复制代码
当前 n = 5
调用 factorial(4)
所以不是存在多条不同的递归指令，而是同一条机器指令在不同调用状态下被反复执行。
十八、CPU如何回到上一层函数
在传统 x86 架构中，call 指令通常会保存返回地址，然后跳转到目标函数。
概念过程：
text
复制代码
执行 call factorial
│
├── 保存下一条指令地址
│
└── 跳转到 factorial 函数入口
被调用函数结束时执行：
asm
复制代码
ret
概念过程：
text
复制代码
执行 ret
│
├── 取出之前保存的返回地址
│
└── 跳回调用者继续执行
例如当前层执行：
cpp
复制代码
int childResult = factorial(n - 1);
int result = n * childResult;
子函数返回后，程序会回到第一行调用表达式之后，然后继续执行：
cpp
复制代码
int result = n * childResult;
这就是外层函数能够"恢复"的原因。
十九、通过局部变量地址观察递归层次
下面的程序为每一层递归创建一个局部变量，并打印它的地址。
不同递归层中的局部变量通常具有不同地址，可以直观看出每次调用都拥有独立的局部状态。
cpp
复制代码
#include
#include
#include
#if defined(_MSC_VER)
#define NOINLINE __declspec(noinline)
#elif defined(__GNUC__) || defined(__clang__)
#define NOINLINE __attribute__((noinline))
#else
#define NOINLINE
#endif
NOINLINE std::uint64_t factorialTrace(
unsigned int n,
unsigned int depth = 0)
{
int frameMarker = 0;
const std::string indent(depth * 4, ' ');
std::cout
<< indent
<< "进入 factorial(" << n << ")"
<< "，局部变量地址："
<< static_cast
<< '\n';
if (n <= 1)
{
std::cout
<< indent
<< "命中终止条件，返回 1\n";
return 1;
}
std::cout
<< indent
<< "当前层暂时等待，调用 factorial("
<< n - 1
<< ")\n";
const std::uint64_t childResult =
factorialTrace(n - 1, depth + 1);
const std::uint64_t result =
static_cast
std::cout
<< indent
<< "恢复 factorial(" << n << ")："
<< n << " × " << childResult
<< " = " << result
<< '\n';
return result;
}
int main()
{
constexpr unsigned int n = 6;
const std::uint64_t result =
factorialTrace(n);
std::cout
<< "\n最终结果："
<< n
<< "! = "
<< result
<< '\n';
return 0;
}
编译：
bash
复制代码
g++ -std=c++17 -O0 -fno-omit-frame-pointer \
-Wall -Wextra -pedantic \
main.cpp -o recursion_demo
运行：
bash
复制代码
./recursion_demo
输出示例：
text
复制代码
进入 factorial(6)，局部变量地址：0x7ffd00001000
当前层暂时等待，调用 factorial(5)
进入 factorial(5)，局部变量地址：0x7ffd00000fa0
当前层暂时等待，调用 factorial(4)
进入 factorial(4)，局部变量地址：0x7ffd00000f40
当前层暂时等待，调用 factorial(3)
进入 factorial(3)，局部变量地址：0x7ffd00000ee0
当前层暂时等待，调用 factorial(2)
进入 factorial(2)，局部变量地址：0x7ffd00000e80
当前层暂时等待，调用 factorial(1)
进入 factorial(1)，局部变量地址：0x7ffd00000e20
命中终止条件，返回 1
恢复 factorial(2)：2 × 1 = 2
恢复 factorial(3)：3 × 2 = 6
恢复 factorial(4)：4 × 6 = 24
恢复 factorial(5)：5 × 24 = 120
恢复 factorial(6)：6 × 120 = 720
最终结果：6! = 720
地址值因运行环境而不同。
栈地址向高地址还是低地址变化也属于平台实现细节。
真正需要关注的是：
text
复制代码
每一层递归调用中的局部变量地址通常不同，
说明它们是相互独立的变量实例。
二十、使用显式栈模拟递归
递归阶乘会隐式保存尚未完成的乘法：
text
复制代码
6 × ...
5 × ...
4 × ...
3 × ...
2 × ...
也可以使用 std::stack 手动保存这些数字。
cpp
复制代码
#include
#include
#include
#include
std::uint64_t factorialWithStack(unsigned int n)
{
if (n > 20)
{
throw std::overflow_error(
"结果超过 uint64_t 可表示范围");
}
std::stack
while (n > 1)
{
std::cout << "压栈：" << n << '\n';
pendingNumbers.push(n);
--n;
}
std::uint64_t result = 1;
while (!pendingNumbers.empty())
{
const unsigned int current =
pendingNumbers.top();
pendingNumbers.pop();
std::cout
<< "出栈：" << current
<< "，计算 "
<< current
<< " × "
<< result;
result *= current;
std::cout
<< " = "
<< result
<< '\n';
}
return result;
}
int main()
{
const std::uint64_t result =
factorialWithStack(6);
std::cout
<< "最终结果："
<< result
<< '\n';
return 0;
}
运行结果：
text
复制代码
压栈：6
压栈：5
压栈：4
压栈：3
压栈：2
出栈：2，计算 2 × 1 = 2
出栈：3，计算 3 × 2 = 6
出栈：4，计算 4 × 6 = 24
出栈：5，计算 5 × 24 = 120
出栈：6，计算 6 × 120 = 720
最终结果：720
递归与显式栈的对应关系：
text
复制代码
递归调用阶段 显式栈
factorial(6) push(6)
factorial(5) push(5)
factorial(4) push(4)
factorial(3) push(3)
factorial(2) push(2)
factorial(1) result = 1
递归返回阶段 显式栈
factorial(2) 返回 pop(2)
factorial(3) 返回 pop(3)
factorial(4) 返回 pop(4)
factorial(5) 返回 pop(5)
factorial(6) 返回 pop(6)
两种实现保存的是同一类信息：
text
复制代码
还有哪些乘法尚未执行
每一步返回后应该继续做什么
区别在于：
text
复制代码
递归版本：
由函数调用机制隐式保存。
显式栈版本：
由程序员通过 std::stack 主动保存。
二十一、递归也可以改写成循环
阶乘并不一定需要递归。
循环实现：
cpp
复制代码
#include
#include
std::uint64_t factorialIterative(unsigned int n)
{
if (n > 20)
{
throw std::overflow_error(
"结果超过 uint64_t 可表示范围");
}
std::uint64_t result = 1;
for (unsigned int i = 2; i <= n; ++i)
{
result *= i;
}
return result;
}
计算 6!：
text
复制代码
result = 1
result = 1 × 2 = 2
result = 2 × 3 = 6
result = 6 × 4 = 24
result = 24 × 5 = 120
result = 120 × 6 = 720
循环版本不需要保存所有等待完成的函数调用。
它只需要维护：
text
复制代码
当前循环变量
累计结果
因此空间复杂度更低。
二十二、递归、显式栈和循环的区别
实现方式
状态保存位置
时间复杂度
额外空间复杂度
普通递归
函数调用状态
O(n)
O(n)
显式栈
std::stack
O(n)
O(n)
普通循环
累计变量
O(n)
O(1)
对于阶乘问题，循环实现通常更直接。
但是在树、图、分治、回溯等问题中，递归代码通常更接近问题本身的结构。
二十三、为什么树结构适合递归
二叉树本身具有递归结构。
一棵二叉树可以定义为：
text
复制代码
一个根结点
一棵左子树
一棵右子树
左子树和右子树本身又是二叉树。
因此前序遍历可以写成：
cpp
复制代码
void preorder(TreeNode* root)
{
if (root == nullptr)
{
return;
}
std::cout << root->value << ' ';
preorder(root->left);
preorder(root->right);
}
每一层调用负责一个结点：
text
复制代码
处理当前结点
递归处理左子树
递归处理右子树
调用栈会自动保存：
text
复制代码
当前处理到哪个结点
左子树是否已经处理
右子树是否仍待处理
返回上一层的位置
这比手动维护大量中间状态更加自然。
二十四、直接递归与间接递归
1. 直接递归
函数直接调用自身：
cpp
复制代码
void function(int n)
{
if (n <= 0)
{
return;
}
function(n - 1);
}
调用关系：
text
复制代码
function(3)
↓
function(2)
↓
function(1)
↓
function(0)
2. 间接递归
函数经过其他函数再次调用自身：
cpp
复制代码
void functionB(int n);
void functionA(int n)
{
if (n <= 0)
{
return;
}
functionB(n - 1);
}
void functionB(int n)
{
if (n <= 0)
{
return;
}
functionA(n - 1);
}
调用关系：
text
复制代码
functionA
↓
functionB
↓
functionA
↓
functionB
无论直接递归还是间接递归，每次函数调用都需要独立的调用状态。
二十五、递归调用和普通函数调用没有本质区别
普通函数调用：
cpp
复制代码
void functionA()
{
functionB();
}
递归调用：
cpp
复制代码
void functionA()
{
functionA();
}
对函数调用机制而言，两者都是：
text
复制代码
保存调用者状态
准备被调用函数参数
跳转到被调用函数
等待返回
恢复调用者状态
继续执行
区别只是：
text
复制代码
普通调用：跳转到另一个函数；
递归调用：跳转到当前函数自身。
递归不是一种特殊的处理器指令，也不是编译器复制函数代码。
它只是普通函数调用的一种特殊调用关系。
二十六、递归深度
递归深度表示同一时刻存在多少层尚未返回的递归调用。
调用：
cpp
复制代码
factorial(6);
最大递归深度大约为：
text
复制代码
6
因为最深时存在：
text
复制代码
factorial(6)
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
不同算法的递归深度并不相同。
阶乘：
text
复制代码
每次 n 减少 1
递归深度：O(n)
递归二分查找：
text
复制代码
每次问题规模缩小一半
递归深度：O(log n)
平衡二叉树遍历：
text
复制代码
递归深度与树高有关
平衡树通常为 O(log n)
退化二叉树：
text
复制代码
树高可能为 O(n)
递归深度也可能为 O(n)
二十七、什么是栈溢出
线程栈空间不是无限的。
如果递归层数过深，每一层都创建新的调用状态，最终可能耗尽栈空间。
例如：
cpp
复制代码
void infiniteRecursion()
{
infiniteRecursion();
}
调用过程：
text
复制代码
infiniteRecursion()
infiniteRecursion()
infiniteRecursion()
...
没有终止条件，调用栈不断增长。
最终可能出现：
text
复制代码
Stack overflow
Segmentation fault
程序异常终止
不同系统中的具体表现可能不同。
递归函数必须保证：
text
复制代码
存在可到达的终止条件；
每一次递归都更加接近终止条件。
二十八、尾递归
当递归调用是函数返回前的最后一个操作时，称为尾递归。
例如：
cpp
复制代码
#include
std::uint64_t factorialTail(
unsigned int n,
std::uint64_t result)
{
if (n <= 1)
{
return result;
}
return factorialTail(
n - 1,
result * n);
}
调用：
cpp
复制代码
factorialTail(6, 1);
过程：
text
复制代码
factorialTail(6, 1)
factorialTail(5, 6)
factorialTail(4, 30)
factorialTail(3, 120)
factorialTail(2, 360)
factorialTail(1, 720)
当前层不需要等待子调用返回后再进行额外计算。
某些编译器可能将尾递归优化成循环，从而复用调用状态。
但是：
C++ 标准不保证编译器一定执行尾调用优化。
因此，在对调用深度敏感的代码中，不能只因为函数是尾递归，就假设它一定使用 O(1) 栈空间。
直接写成循环通常更明确。
二十九、C++标准是否规定递归必须使用物理栈
C++ 标准规定程序行为，但通常不规定函数调用必须采用哪一种底层实现。
编译器可以：
text
复制代码
使用物理调用栈
使用寄存器
内联函数
消除不必要的调用
执行尾调用优化
把递归变换成循环
因此，严格说法是：
语言语义要求每次尚未结束的函数调用拥有独立状态；主流 C++ 实现通常通过调用栈和寄存器保存这些状态。
在开启优化后，编译器可能改变甚至消除部分栈帧。
因此观察汇编和调试调用栈时，通常使用：
text
复制代码
-O0
-fno-omit-frame-pointer
降低优化带来的干扰。
三十、使用 GDB 观察递归调用栈
示例代码：
cpp
复制代码
#include
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
return n * factorial(n - 1);
}
int main()
{
std::cout << factorial(6) << '\n';
return 0;
}
编译：
bash
复制代码
g++ -std=c++17 -O0 -g \
-fno-omit-frame-pointer \
main.cpp -o recursion_demo
启动 GDB：
bash
复制代码
gdb ./recursion_demo
为函数设置断点：
gdb
复制代码
break factorial
运行：
gdb
复制代码
run
每次暂停后查看参数：
gdb
复制代码
info args
继续执行：
gdb
复制代码
continue
当进入 factorial(1) 时，查看完整调用栈：
gdb
复制代码
backtrace
也可以使用缩写：
gdb
复制代码
bt
典型结果：
text
复制代码
#0 factorial(int) n=1
#1 factorial(int) n=2
#2 factorial(int) n=3
#3 factorial(int) n=4
#4 factorial(int) n=5
#5 factorial(int) n=6
#6 main()
每一行代表一次尚未结束的函数调用。
切换到指定栈帧：
gdb
复制代码
frame 3
查看该层参数：
gdb
复制代码
info args
查看局部变量：
gdb
复制代码
info locals
这样可以直接观察不同递归层中的独立参数。
三十一、完整时序图
调用：
cpp
复制代码
factorial(4);
完整执行过程：
text
复制代码
main
│
│ 调用 factorial(4)
▼
factorial(4)
│
│ 保存当前 n = 4
│ 等待 factorial(3) 的结果
▼
factorial(3)
│
│ 保存当前 n = 3
│ 等待 factorial(2) 的结果
▼
factorial(2)
│
│ 保存当前 n = 2
│ 等待 factorial(1) 的结果
▼
factorial(1)
│
│ 命中递归终止条件
│ 返回 1
▼
factorial(2)
│
│ 恢复 n = 2
│ 计算 2 × 1
│ 返回 2
▼
factorial(3)
│
│ 恢复 n = 3
│ 计算 3 × 2
│ 返回 6
▼
factorial(4)
│
│ 恢复 n = 4
│ 计算 4 × 6
│ 返回 24
▼
main
对应的栈变化：
text
复制代码
递归深入：
push factorial(4)
push factorial(3)
push factorial(2)
push factorial(1)
递归返回：
pop factorial(1)
pop factorial(2)
pop factorial(3)
pop factorial(4)
这里的 push 和 pop 是概念描述，不是 C++ 源代码中的显式函数调用。
三十二、递归函数的基本编写模板
一般递归函数可以抽象为：
cpp
复制代码
ReturnType recursiveFunction(Problem problem)
{
if (到达最小问题)
{
return 基础结果;
}
SmallerProblem smaller =
缩小问题规模(problem);
ReturnType childResult =
recursiveFunction(smaller);
return 使用子问题结果解决当前问题(
problem,
childResult);
}
对应阶乘：
cpp
复制代码
int factorial(int n)
{
if (n <= 1)
{
return 1;
}
int smaller = n - 1;
int childResult =
factorial(smaller);
return n * childResult;
}
三十三、正确递归的三个必要条件
1. 必须存在终止条件
cpp
复制代码
if (n <= 1)
{
return 1;
}
没有终止条件，递归无法停止。
2. 每次递归必须缩小问题
cpp
复制代码
factorial(n - 1);
下一层比当前层更接近终止条件。
错误示例：
cpp
复制代码
factorial(n);
问题规模没有变化，会无限递归。
错误示例：
cpp
复制代码
factorial(n + 1);
问题规模不断增大，离终止条件越来越远。
3. 当前问题必须依赖子问题结果
cpp
复制代码
return n * factorial(n - 1);
当前层需要使用子问题结果：
text
复制代码
factorial(n - 1)
计算：
text
复制代码
n × factorial(n - 1)
这样递归才能逐层返回最终结果。
三十四、常见误区
1. 认为代码中没有 std::stack 就没有使用栈
函数调用栈和 std::stack 不是同一个概念。
text
复制代码
函数调用栈：
管理函数参数、返回地址和调用状态。
std::stack：
程序员显式使用的数据结构。
递归通常使用前者。
2. 认为递归会复制多份函数代码
函数代码通常只有一份。
每次递归调用创建的是新的调用状态，而不是新的代码副本。
text
复制代码
代码：一份
状态：多份
3. 认为所有递归层共享同一个参数
不同调用中的同名参数是不同变量实例。
text
复制代码
factorial(6) 中的 n = 6
factorial(5) 中的 n = 5
factorial(4) 中的 n = 4
它们属于不同调用。
4. 认为外层函数已经执行结束
当 factorial(6) 调用 factorial(5) 时，factorial(6) 并没有结束。
它只是等待子调用返回。
只有完成：
text
复制代码
6 × factorial(5) 的返回值
之后，它才能返回。
5. 认为递归函数在并行执行
普通递归通常只有一个线程顺序执行。
外层暂停，内层执行；内层返回后，外层恢复。
6. 认为函数返回后所有信息都会丢失
当前层调用在子函数执行期间仍然存在。
它的参数、返回位置和后续操作会被保存。
子函数返回后，当前层可以继续执行。
7. 忽略整数溢出
使用 32 位 int 计算阶乘时：
text
复制代码
12! = 479001600
13! = 6227020800
13! 已经超过典型 32 位有符号整数最大值：
text
复制代码
2147483647
因此不应使用 int 计算较大的阶乘。
std::uint64_t 通常最多保存到：
text
复制代码
20!
三十五、安全的阶乘完整代码
cpp
复制代码
#include
#include
#include
std::uint64_t factorial(unsigned int n)
{
if (n > 20)
{
throw std::overflow_error(
"n 不能大于 20，结果会超过 uint64_t 范围");
}
if (n <= 1)
{
return 1;
}
const std::uint64_t childResult =
factorial(n - 1);
return static_cast
* childResult;
}
int main()
{
unsigned int n = 0;
std::cout << "请输入 0 到 20 之间的整数：";
if (!(std::cin >> n))
{
std::cerr << "输入格式错误\n";
return 1;
}
try
{
const std::uint64_t result =
factorial(n);
std::cout
<< n
<< "! = "
<< result
<< '\n';
}
catch (const std::exception& exception)
{
std::cerr
<< "计算失败："
<< exception.what()
<< '\n';
return 1;
}
return 0;
}
编译：
bash
复制代码
g++ -std=c++17 -Wall -Wextra -pedantic \
main.cpp -o factorial_demo
运行：
bash
复制代码
./factorial_demo
三十六、复杂度分析
递归阶乘：
cpp
复制代码
factorial(n);
每次将问题从 n 缩小为：
text
复制代码
n - 1
总调用次数约为：
text
复制代码
n
因此时间复杂度为：
text
复制代码
O(n)
最大调用深度也约为：
text
复制代码
n
每一层需要保存调用状态，所以额外空间复杂度为：
text
复制代码
O(n)
循环阶乘：
cpp
复制代码
for (unsigned int i = 2; i <= n; ++i)
{
result *= i;
}
时间复杂度同样是：
text
复制代码
O(n)
但只使用固定数量变量，所以额外空间复杂度为：
text
复制代码
O(1)
三十七、递归执行模型总结
调用：
cpp
复制代码
factorial(6);
运行时不是展开出六份源代码，而是同一份函数代码被调用六次。
每次调用都有独立状态：
text
复制代码
factorial(6)：n = 6
factorial(5)：n = 5
factorial(4)：n = 4
factorial(3)：n = 3
factorial(2)：n = 2
factorial(1)：n = 1
递归深入阶段：
text
复制代码
factorial(6)
↓
factorial(5)
↓
factorial(4)
↓
factorial(3)
↓
factorial(2)
↓
factorial(1)
递归返回阶段：
text
复制代码
factorial(1) = 1
↑
factorial(2) = 2 × 1 = 2
↑
factorial(3) = 3 × 2 = 6
↑
factorial(4) = 4 × 6 = 24
↑
factorial(5) = 5 × 24 = 120
↑
factorial(6) = 6 × 120 = 720
整个过程可以概括为：
text
复制代码
当前调用执行到递归语句
↓
保存当前调用状态
↓
进入规模更小的子调用
↓
到达终止条件
↓
子调用返回结果
↓
恢复上一层调用状态
↓
完成上一层剩余计算
↓
继续逐层返回
三十八、最终结论
递归并不是凭空实现多层函数调用，也不是编译器提前复制多份函数代码。
它依赖普通函数调用机制。
每次递归调用都会形成一个独立的函数调用状态，保存：
text
复制代码
当前参数
局部变量
返回地址
未完成的计算
必要的寄存器状态
在主流 C++ 实现中，这些状态通常由调用栈和寄存器共同管理。
源代码中不需要手动创建 std::stack，是因为函数调用机制已经自动完成了类似的状态压入和恢复过程。
递归的本质可以概括为：
使用函数调用自动保存当前问题的执行状态，先解决更小的子问题，再根据子问题结果恢复并完成当前问题。
对于阶乘：
text
复制代码
递：不断保存 n，并进入 factorial(n - 1)
归：从 factorial(1) 开始返回，
逐层完成 n × 子问题结果
因此，递归中的"栈"并没有消失，只是由底层函数调用机制隐式维护。