45f9d30a

Стековая организация рекурсии


В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор end, закрывающий подпрограмму, либо в ее тексте встретится оператор exit, насильственно прерывающий ее выполнение.

Если некоторая подпрограмма в процессе выполнения вызывает другую подпрограмму, то для вызванной процедуры или функции создается новый отдельный контекст (контекст вызвавшей подпрограммы при этом сохраняется) и т.д. Активным в каждый момент времени является последний контекст. После ликвидации текущего активного контекста активным становится последний "отложенный" контекст - тот, из которого только что закрытый и был вызван.

Таким образом, на внутреннем уровне организован стек контекстов подпрограмм.

Проследим состояние стека контекстов на примере рекурсивной процедуры, решающей задачу разложения натурального числа на сомножители всеми возможными способами (без повторений):

procedure razlozh(k,t:integer; s:string); var i: integer; sss: string; begin for i:= t to trunc(sqrt(k)) do if k mod i = 0 then begin str(i,sss); razlozh(k div i, i,s+sss+'*'); end; str(k,sss); s:=s+sss; writeln(s); end; begin readln(n); razlozh(n,2,''); end.

Для n = 24 стек контекстов этой программы пройдет последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста):

4k3
t2
s2*2*2
3k63k63k4
t2t2t3
s2*2s2*2s2*3*
2k122k122k122k122k82k6
t2t2t2t2t3t4
s2*s2*s2*s2*s3*s4*
1k241k241k241k241k241k241k24
t2t2t2t2t2t2t2
sssssss

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

2*2*2*3 2*2*6 2*3*4 2*12 3*8 4*6 24



Содержание раздела