Нужна ли обработка рекурсии специальной обработки при разработке компилятора?

Question

Вызовы функций обрабатываются через структуру данных стека. Достаточно ли этого для поддержки рекурсии?

Answer 1

Вообще иметь стек является Специальное лечение, которое компилятор должен иметь при поддержке рекурсии.

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

Введение стека функций - это то, что сначала включила рекурсию, фактически выражается на языке программирования. До этого программисты будут использовать рекурсию в качестве инструмента для абстрактного решения проблемы, но затем придется перевести этот код в итерационную логику из -за отсутствия стека вызовов.

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

Надеюсь это поможет!