GrabDuck

Как реализована рекурсия на уровне компилятора (если так будет правильно сказать)?

:

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

Теперь по поводу локальных переменных (и параметров). Они располагаются в так называемом activation record'е данной функции. Каждая функция знает, явно или неявно, свой activation record, и производит доступ к локальным переменным через него. При начале работы функции создаётся её индивидуальный activation record, поэтому при возвращении из (рекурсивного или нет) вызова функция всё так же работает со своими переменными. При вызове другой функции выполнение переключается на новый activation record, а при возврате активируется прежний.

Для языков, произошедших от C, обычное место для activation record'а — стек. Это сделано так, потому что вызванная функция заканчивает обработку строго перед возвратом в вызывающую функцию, и таким образом activation record'ы подчиняются дисциплине «последний пришёл — первый ушёл». Для этого случая activation record обычно называют stack frame. Активизация stack frame'а обычно сводится к (сохранению и) изменению значения в специальном регистре, указывающем на текущий frame.

Часто переменные располагаются в регистрах процессора для ускорения доступа. В этом случае при смене activation record'а «живые» переменные всё равно должны быть сохранены в некоторой области памяти, и восстановлены, когда activation record снова активизируется.

Для языков, в которых части функции могут пережить её выполнение (сопрограммы, лямбда-функции, continuation passing style и т. п.) activation record не всегда может находится в стеке, и им управляет рантайм-билиотека. Обычное их размещение в этом случае — free store (heap).


Некоторые языки (например, Pascal), позволяют вложенные функции, так что внутренняя функция имеет доступ к переменным внешней функции. В этом случае activation record соджержит т. наз. static chain — указатель на activation record внешней функции. Обратите внимание, что «внешняя функция» имеется в виду в лексическом смысле (функция, содержащая внутреннюю функцию, а не вызвавшая её), из-за возможной рекурсии во вложенных функциях. (И имеется в виду activation record самого ближнего экземпляра внешней функции.)

Указатель на свой activation record, соответственно, называют dynamic chain.

В языках без вложенных функций (наподобие C) static chain не требуется.