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;
}

Answer 1

«Стек» в современных архитектурах ЦП - это область памяти (отдельная для каждого потока), в которой, помимо прочего, хранится адрес возврата при вызове функции, параметры вызова функции, нестатические локальные переменные (обычнов таком порядке, но не всегда). Каждый раз, когда любая функция вызывается в C (и в большинстве современных языков), адрес возврата (адрес, к которому нужно перейти, когда функция, которая должна быть вызвана, завершает выполнение) помещается в стек, а указатель стека увеличивается на размерадрес (при условии, что стек увеличивается), затем каждый параметр функции помещается в стек, и указатель стека снова увеличивается на размер каждого параметра. Поскольку каждой локальной переменной функции выделяется пространство, указатель стека увеличивается на размер этой переменной, когда он помещается в стек. Когда функция возвращается, указатель стека «разматывается» на значение размера каждой переменной, помещенной в стек, так как они выталкиваются из стека. Затем параметры вызова функции извлекаются из стека, и снова указатель стека уменьшается на размер каждого параметра. Наконец, функция переходит на адрес возврата, который был изначально помещен в стек при вызове функции, и он выталкивается, а указатель стека уменьшается на размер адреса. Теперь мы готовы выполнить любой код, следующий за вызовом функции, и указатель стека вернется туда, где он был до вызова функции.

В случае рекурсивных вызовов функций адрес возврата, параметры вызова функциии локальные переменные функции помещаются в стек для каждого вызова вложенной функции, но не извлекаются из стека до тех пор, пока не завершится последний рекурсивный вызов функции. Они выталкиваются из стека в порядке, обратном тому, как они были помещены в стек (так как стеки по своей природе являются последними в порядке поступления, LIFO, структуры данных).

Предполагается, что это выполняется на 32-битном ЦП и'int' составляет 4 байта, тогда адрес возврата для каждого рекурсивного вызова функции плюс один параметр функции будут помещены в стек. При максимальном использовании стека непосредственно перед возвратом test(0) мы получим 6-кратные рекурсивные вызовы (для 5,4,3,2,1,0) и 32-битный (4-байтовый) адрес возврата плюс 4-байтовый параметрдля каждого вызова 6 * (4 + 4) = 48 байт.

Answer 2

Каждый экземпляр test получает свой собственный экземпляр i. Когда вы вызываете функцию, текущая среда выполнения текущей функции сохраняется, и для новой функции устанавливается контекст. Когда эта новая функция возвращается, контекст вызывающей функции восстанавливается.