Блог

Известно, что для моделирования семантики процедур во время выполнения обычно необходим стек. Если язык не допускает рекурсию процедур, должны ли у нас быть стеки? И если язык допускает рекурсию процедур, но рекурсивный вызов может выполняться только в конце процедуры, должны ли у нас быть стеки?

В Fortran, который вас, вероятно, интересует в качестве примера, вам нужен стек для рекурсии. Это потому, что вы хотите, чтобы локальные переменные рекурсивных процедур были независимыми при каждом вызове процедуры. Не все должны быть независимыми, но обычно вы хотите иметь такую возможность.

Без рекурсии у вас есть только один вызов любой процедуры в любое время, поэтому локальные переменные могут быть статическими. Не так с рекурсией, вы не знаете, насколько глубокой она будет, поэтому вам нужна некоторая динамическая структура данных для хранения данных. При необходимости вы можете эмулировать стек в куче, но вам нужна некоторая динамическая память.

Часто стек также используется для автоматических массивов (переменной длины), но это не обязательно, они могут находиться в куче в зависимости от компилятора и его настроек.

Стек используется для хранения адреса возврата, который будет достигнут после завершения выполнения метода. Стек также используется для выделения объектов с ограниченной областью действия.

Итак, если ваш язык запуска не разрешает автоматические объекты (в стиле C) (или, другими словами, не разрешает локальные области) или не разрешает методы, я полагаю, что язык может полностью исключить реализацию стека.

Я думаю, что рекурсия не имеет ничего общего с требованием стека.