c - C 递归与内存

Question

1. 计算机如何将每个更改'i'的值保存在内存中并打印出来？

2. 此代码中使用了多少字节？24 个字节（i = 5、4、3、2、1、0）还是只有 4 个字节？

以下代码打印：1、2、3、4、5。

#include <stdio.h>

void test(int i)
{
    if (i == 0) return;
    test(i - 1);
    printf("%d\n", i);
}

int main(void)
{
    test(5);
    return 0;
}

标签： crecursion

Answer 1

现代 CPU 架构上的“堆栈”是一个内存区域（每个线程分开），其中存储了函数调用时的返回地址、函数调用参数、非静态局部变量（通常按此顺序） ， 但不总是）。每次在 C（和大多数现代语言）中调用任何函数时，返回地址（即将被调用的函数完成执行后跳转到的地址）被压入堆栈，堆栈指针增加一个地址（假设堆栈增长），然后将每个函数参数压入堆栈，堆栈指针再次增加每个参数的大小。由于每个函数局部变量都被分配了空间，因此堆栈指针会随着该变量的大小增加，因为它被压入堆栈。当函数返回时，堆栈指针被压入堆栈的每个变量的大小值“展开”，因为它们从堆栈中弹出。接下来，函数调用参数从堆栈中弹出，堆栈指针再次按每个参数的大小递减。最后，函数跳转到函数调用时最初压入堆栈的返回地址，并将其弹出，堆栈指针递减一个地址的大小。我们现在准备执行函数调用之后的任何代码，堆栈指针正好回到函数调用之前的位置。接下来，函数调用参数从堆栈中弹出，堆栈指针再次按每个参数的大小递减。最后，函数跳转到函数调用时最初压入堆栈的返回地址，并将其弹出，堆栈指针递减一个地址的大小。我们现在准备执行函数调用之后的任何代码，堆栈指针正好回到函数调用之前的位置。接下来，函数调用参数从堆栈中弹出，堆栈指针再次按每个参数的大小递减。最后，函数跳转到函数被调用时最初压入堆栈的返回地址，并将其弹出，堆栈指针递减一个地址的大小。我们现在准备执行函数调用之后的任何代码，堆栈指针正好回到函数调用之前的位置。

在递归函数调用的情况下，每个嵌套函数调用的返回地址、函数调用参数和函数局部变量都被压入堆栈，但在最终的递归函数调用返回之前不会从堆栈中弹出。它们以与压入堆栈相反的顺序从堆栈中弹出（因为堆栈本质上是后进先出、LIFO、数据结构）。

假设这是在 32 位 CPU 上执行的，并且“int”是 4 个字节，那么每个递归函数调用的返回地址，加上一个函数参数将被压入堆栈。在堆栈利用率最高的情况下，在test(0)返回之前，我们将有 6 次递归调用（对于 5、4、3、2、1、0）和一个 32 位（4 字节）的返回地址，以及每个调用的 4 字节参数，所以 6 * (4 + 4) = 48 个字节。