程序执行与内存

用递归和动态数据结构串起算法、函数调用、CPU、进程地址空间与虚拟存储。

一句话模型

递归在算法层把一个问题不断拆成规模更小的同类问题。程序运行时，每次递归调用都会创建一个栈帧，用来保存这一层调用的参数、局部变量和返回位置。若递归过程中通过 malloc 创建链表或树的结点，这些对象会保存在堆中；程序使用指针访问结点时，虚拟地址经过页表翻译，最终访问 Cache 或主存中的数据。

三层递进

简单：只看一次递归调用如何创建栈帧，并在递归返回时销毁栈帧。
中等：加入动态创建的树结点，区分“栈上的执行现场”和“堆上的长期对象”。
复杂：从 C 源码出发，经过编译器、指令、CPU、虚拟地址翻译、Cache 和主存，解释一次函数调用和指针访问如何真正执行。

简单图谱：递归与函数调用栈

递归并不是 CPU 的特殊功能。递归函数会被编译为普通的函数调用，每次调用建立一个新的栈帧；到达终止条件后，再按照后进先出的顺序逐层返回。

# 递归执行

## 算法层

- 定义子问题
- 设置递归终止条件
- 递归调用
- 合并子问题结果

## 运行时层

- CALL 保存返回位置并转移控制流
- 建立 callee 栈帧
- 保存参数、局部变量和寄存器
- RET 恢复 caller 并继续执行

## 复杂度

- 同时存在的栈帧数量等于递归深度
- 每层栈帧空间乘以最大深度得到调用栈空间
- 递归过深可能发生栈溢出

基础知识页面：算法复杂度、函数定义和调用、函数调用时内存结构。

中等图谱：栈帧与堆对象同时存在

主干问题是：递归创建一棵树时，哪些数据随着函数返回而消失，哪些数据在返回后仍然存在？

先把递归调用和 malloc 放回完整的进程虚拟地址空间：递归调用使用栈区保存执行现场，malloc 从堆区或内存映射区域取得动态对象空间。

图中最重要的关系是：栈帧中的 node 是一个指针变量，而它指向的 TreeNode 才是堆对象。两者位于不同的内存区域，也具有不同的生命周期。

再放大递归构造二叉树的过程，观察多个栈帧如何创建堆中的多个结点：

可以用下面的简化代码理解：

TreeNode *build(int depth) {
    if (depth == 0) return NULL;

    TreeNode *node = malloc(sizeof(TreeNode));
    node->left = build(depth - 1);
    node->right = build(depth - 1);
    return node;
}

depth、node 这个指针变量和返回地址属于当前调用的栈帧。
malloc 创建的 TreeNode 对象位于堆中，栈帧只保存指向它的指针。
递归返回会销毁当前栈帧，但不会自动释放堆中的树结点。
最外层调用者仍可通过根指针访问整棵树；不再使用时需要遍历并 free 每个结点。

复杂图谱：从源码到物理内存

复杂图把算法、指令、进程地址空间和存储系统叠加起来。一条 C 语句并不会直接操作“树”，CPU 最终执行的是调用、算术、加载和存储指令。

阅读时沿三条路径追踪：

控制流路径：递归源码 → 编译器生成 CALL/RET → PC 改变 → SP/BP 建立或销毁栈帧。
数据生命周期路径：malloc → 用户态堆分配器 → 堆或内存映射区 → 树结点 → free 回收。
实际访存路径：虚拟地址 → TLB/页表 → 物理地址 → Cache → 主存；页面尚未驻留时触发缺页。

子模块图谱：动态数据生命周期

malloc 不是“每调用一次就向操作系统申请一个物理页”。它通常先从用户态分配器已经管理的堆块中分配；空间不足时才通过 brk 或 mmap 等机制扩展虚拟地址空间，页面也可能在第一次访问时才真正获得物理页框。

动态对象的完整生命周期是：提出大小需求 → 分配器查找并切分空闲块 → 必要时向操作系统扩展虚拟空间 → 首次访问触发按需分配 → 指针连接成链表/树/图 → 删除结构时逐个 free → 合并空闲块 → 条件允许时归还部分页面。

子模块图谱：三个容易混淆的“栈”

栈 ADT 是后进先出的逻辑结构，可以用数组或链表实现。
函数调用栈 是进程虚拟地址空间中的运行时区域，由编译器约定和 CPU 指令共同使用。
递归调用 是一种程序控制结构，通常借助函数调用栈保存每层执行现场。

关键问题

递归为什么会消耗额外空间？

每个尚未返回的调用都要保留参数、局部变量、返回地址和部分寄存器。最大递归深度决定同时存在的栈帧数量，而不是递归调用的总次数。

栈上的指针和堆上的对象是什么关系？

指针变量可以位于栈帧，但它保存的虚拟地址可以指向堆对象。栈帧销毁只会让指针变量失效，不会自动释放它指向的堆内存。

为什么 malloc 成功不代表物理内存已经准备好？

分配器可能只返回一段可用虚拟地址。进程第一次读写对应页面时，页表项尚未建立或页面尚未驻留，操作系统才通过缺页处理分配物理页框。

递归、栈溢出和内存泄漏有什么区别？

递归过深可能耗尽有限的调用栈；内存泄漏是堆对象失去可达指针却没有被释放。前者与调用深度有关，后者与动态对象生命周期管理有关。

旁路清单

数据结构：树/图递归遍历、链式存储、递归空间复杂度
指令系统：CALL、RET、PUSH、POP、栈寻址和调用约定
CPU：PC、SP、BP、通用寄存器、加载/存储指令
进程内存：代码区、数据区、堆、栈和内存映射区域
动态分配：空闲链表、块切分、相邻合并、碎片和伙伴算法
虚拟存储：页表、TLB、缺页、页框分配和页面置换
存储层次：Cache 命中/未命中、主存访问和局部性

对应页面：栈、二叉树、链表、函数调用、进程内存空间、内存管理、虚拟存储器。