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

#память #рекурсия #компилятор

Допустим, есть рекурсивная функция, и в ней объявлены локальные переменные. Но, кроме
них, функция еще работает с глобальными переменными (меняет их как-нибудь).
Вопрос: как сохраняются значения локальных и глобальных переменных от одного рекурсивного
вызова к другому и что с ними происходит, так сказать, при "возвращении назад", т.е.
когда рекурсивная функция дошла до конца и передала управление вызвавшему ему? 
Спасибо.    

Ответы

Ответ 1

"На уровне компилятора" никак. Этим интерпретатор занимается... "от одного рекурсивного
вызова к другому" глобальные не сохраняются, на то они и глобальные... Если на одном
шаге изменяете, на следующем будет уже изменённая. Передаваемые функции параметры сохраняются
в стеке, "когда рекурсивная функция дошла до конца" верхние элементы стека передаются
"вызвавшему", стек уменьшается.



Перенес комментарий Isaev в ответ


Ответ 2

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

Теперь по поводу локальных переменных (и параметров). Они располагаются в так называемом
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 не требуется.