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

В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор 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 стек контекстов этой программы пройдет последовательно такие стадии (значения параметров указаны на моменты вызова процедуры, состояния стека приведены только на моменты времени, предшествующие закрытию очередного контекста):

4	k	3
	t	2
	s	222
3	k	6	3	k	6	3	k	4
	t	2		t	2		t	3
	s	2*2		s	2*2		s	23
2	k	12	2	k	12	2	k	12	2	k	12	2	k	8	2	k	6
	t	2		t	2		t	2		t	2		t	3		t	4
	s	2*		s	2*		s	2*		s	2*		s	3*		s	4*
1	k	24	1	k	24	1	k	24	1	k	24	1	k	24	1	k	24	1	k	24
	t	2		t	2		t	2		t	2		t	2		t	2		t	2
	s			s			s			s			s			s			s

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

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

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