递归Flood Fill栈溢出问题：栈内存存储与消耗计算咨询

1. 栈内存存储的内容及存储方式 #

栈内存以**后进先出（LIFO）**的方式存储函数调用过程中的上下文数据，具体包含：

• 函数返回地址：调用当前函数的下一条指令的内存地址，函数执行完成后会跳回该地址继续执行。
• 函数参数：按照平台的调用约定（如cdecl、stdcall）顺序压入栈，通常是从右往左的顺序。
• 局部变量：包括基础数据类型（int、char等）、结构体实例、指针，以及编译器生成的临时变量（如表达式计算的中间值）。
• 栈帧基指针（EBP/RBP）：用于定位当前栈帧内的参数和局部变量，压栈时会保存上一个栈帧的基指针值。
• 寄存器上下文：如果函数使用了被调用者保存的寄存器（如x86架构的EBX、ESI、EDI），会先将这些寄存器的值压入栈，函数结束后再恢复。

所有栈帧在栈内存区域中连续排列，栈指针（ESP/RSP）会随着压栈操作递减、出栈操作递增，始终指向栈顶的位置。

2. 如何计算函数的栈内存消耗 #

静态计算单次函数调用的栈帧大小 #

1. 拆解栈帧组成：
   • 局部变量总大小：注意内存对齐规则（如结构体可能因成员对齐补充padding），编译器可能会优化变量布局减少空间占用。
   • 参数总大小：根据调用约定计算，若函数包含可变参数，需额外考虑这部分的栈空间。
   • 寄存器保存区大小：统计函数用到的被调用者保存寄存器数量，每个寄存器对应栈上的存储大小（x86为4字节，x64为8字节）。
   • 栈帧基指针开销：通常为一个指针的大小（x86为4字节，x64为8字节），若编译器开启了fomit-frame-pointer优化（如-O2级别），这部分开销可忽略。
   • 临时变量开销：编译器可能为复杂表达式、大结构体返回值等分配临时栈空间，需查看汇编代码确认。
2. 借助编译器工具：
   • 使用GCC的-fstack-usage编译选项，会生成.su文件，其中包含每个函数的栈大小估算值。
   • 生成汇编代码（如gcc -S your_code.c），查看栈指针调整指令（如x86的sub $0xXX, %esp，XX即为当前函数栈帧的大小）。

计算递归调用的总栈消耗 #

对于递归Flood Fill，总栈消耗 = 单次递归函数栈帧大小 × 最坏情况下的递归深度 + 调用递归函数前已使用的栈空间。

• 最坏递归深度：即地图中从起点出发的最长可达路径长度（比如M×N网格的最坏深度为M×N）。
• 可用栈内存：不同平台默认栈大小不同（Linux通常为8MB，Windows通常为1MB），可通过ulimit -s（Linux）或链接选项调整；也可通过读取进程内存映射（如Linux的/proc/self/maps）动态计算当前剩余栈空间。

注意事项 #

• 编译器优化（如-O2、-O3）会改变栈帧大小，比如将局部变量放入寄存器、省略栈帧基指针，需以实际编译环境下的计算结果为准。
• 若函数使用变长数组（VLA）等动态局部变量，栈帧大小会动态变化，无法静态计算，需通过运行时栈指针监测来判断。

内容的提问来源于stack exchange，提问作者arzel