为何给C语言递归函数新增1个整型变量未让递归栈深度减半

• 编辑1：根据部分评论建议，我打印了变量的地址。
• 编辑2：根据部分评论建议，我添加了位操作，避免编译器直接优化丢弃我的变量。
• 编辑3：根据一条回答的建议，我修改了变量的打印方式。
• 编辑4：添加了大量无意义操作，增加gcc的优化难度。
• 编辑5：新增代码片段3以测试@4386427的理论——结果似乎支持他的观点，即编译器可能默认预留32 Bytes栈空间，因此我们至少需要定义5个变量才能看出差异。

我对栈内存和堆内存有基础了解。以C语言为例，在函数中定义局部变量会占用栈内存；如果定义指针并为其分配内存块，这些内存块会占用堆内存。如果函数递归调用自身，栈会被占满进而发生溢出。因此我做了一个简单测试，代码片段1和代码片段2的唯一区别是代码片段2多定义了1个整型变量：

代码片段1 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp = rand() % 65536;
  tmp = tmp - 1;
  printf("val: %d; addr: %p; depth: %d\n", tmp, (void*)&tmp, depth);
  tmp = function(++depth) + 1;
  return tmp;
}
int main() {
  srand(time(NULL));
  int res = function(0);
  printf("%d\n", res);
  return 0;
}

输出1 #

...
val: 57227; addr: 0x7fff00dff78c; depth: 174626
val: 8288; addr: 0x7fff00dff75c; depth: 174627
val: 24194; addr: 0x7fff00dff72c; depth: 174628
Segmentation fault

代码片段2 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp0 = rand() % 65536;
  int tmp1 = rand() % 65536;
  tmp0 = tmp0 - 1;
  printf("val: %d, %d; addr: %p, %p; depth: %d\n", tmp0, tmp1, (void*)&tmp0, (void*)&tmp1, depth);
  tmp1 = function(++depth);
  return tmp1 - tmp0;
}
int main() {
  srand(time(NULL));
  int res = function(0);
  printf("%d\n", res);
  return 0;
}

输出2 #

...
val: 40745, 32446; addr: 0x7ffcb80b079c, 0x7ffcb80b0798; depth: 174528
val: 34014, 57470; addr: 0x7ffcb80b076c, 0x7ffcb80b0768; depth: 174529
val: 56801, 34478; addr: 0x7ffcb80b073c, 0x7ffcb80b0738; depth: 174530
Segmentation fault

我使用gcc编译了两段代码，二者均如预期发生栈溢出。但我原本预期，由于代码片段2的函数占用2倍内存，其递归深度会浅得多。然而虽然代码片段2确实更早出现段错误，但二者的栈深度实际上非常接近……
如果按照我的朴素理论推导，代码片段1的函数递归调用174616次，需要占用4 Bytes * 174,616 / 1,024 = 682 KBytes内存；代码片段2的函数递归调用174539次，需要占用(4 + 4) Bytes * 174,539 = 1,363 KBytes内存。
请问为什么会出现这种现象？

代码片段3 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp0 = rand() % 65536;
  int tmp1 = rand() % 65536;
  int tmp2 = rand() % 65536;
  int tmp3 = rand() % 65536;
  int tmp4 = rand() % 65536;
  int tmp5 = rand() % 65536;
  tmp0 = tmp0 - 1;
  tmp1 = tmp1 + 1;
  tmp2 = tmp2 - 2;
  tmp3 = tmp3 + 2;
  tmp4 = tmp4 - 3;
  tmp5 = tmp5 + 3;
  printf("val: %d, %d, %d; addr: %p, %p, %p; depth: %d\n", tmp0, tmp1, tmp2, (void*)&tmp0, (void*)&tmp1, (void*)&tmp2, depth);
  tmp1 = function(++depth);
  return tmp0 - tmp1 + tmp2 - tmp3 + tmp4;
}
int main() {
  srand(time(NULL));
  long res = function(0);
  printf("%d\n", res);
  return 0;
}

输出3 #

val: 9366, 56113, 48970; addr: 0x7fff063fe830, 0x7fff063fe82c, 0x7fff063fe828; depth: 130920
val: 11924, 11633, 26004; addr: 0x7fff063fe7f0, 0x7fff063fe7ec, 0x7fff063fe7e8; depth: 130921
val: 13316, 42397, 45027; addr: 0x7fff063fe7b0, 0x7fff063fe7ac, 0x7fff063fe7a8; depth: 130922
val: 4285, 58053, 21693; addr: 0x7fff063fe770, 0x7fff063fe76c, 0x7fff063fe768; depth: 130923
Segmentation fault

问题解答 #

这个现象是x86架构下gcc默认的栈帧对齐、预留规则导致的：

1. x86_64环境下gcc默认会给每个函数栈帧做16字节对齐，多数系统还会默认预留至少32字节的基础栈空间，用来存放返回地址、基址寄存器、入参拷贝等元数据，你定义的局部变量只是在这个预留的空白空间里填充，只要总大小没超出预留空间，新增局部变量不会增加单栈帧的总占用。
2. 前两个测试里，不管是1个int（4字节）还是2个int（8字节），都远小于默认预留的栈空间，所以两个代码的单栈帧大小几乎没有差异，递归深度自然非常接近，仅有的微小差异是测试环境栈地址随机化导致的正常波动。
3. 第三个测试定义了6个int（总24字节），加上元数据已经超出了默认预留的基础栈空间，此时栈帧总大小才会明显变大，所以递归深度直接降到了13万左右，和前两个测试的17万有了显著差距，刚好验证了栈预留空间的理论。

你可以添加编译参数-fomit-frame-pointer或者调整栈对齐参数-mpreferred-stack-boundary复现测试，能直观看到不同编译规则下栈深度的变化。

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