- •9. Лекция: Рекурсивные подпрограммы Динамические структуры данных: стек, очередь, дек. Рекурсивные процедуры и функции. Сравнение рекурсивных и нерекурсивных алгоритмов. Быстрая сортировка массива.
- •Стековая организация рекурсии
- •Ограничение глубины рекурсии
- •Замена рекурсивных алгоритмов итеративными
- •Реализация нерекурсивного алгоритма
- •Иллюстрация
Стековая организация рекурсии
В момент вызова подпрограммы в памяти создается ее контекст: выделяется место под все ее параметры, локальные переменные и константы. Уничтожается этот контекст только после того, как будет достигнут оператор 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 |
2*2*2 |
|
||||||||||||||||||||||||
3 |
k |
6 |
|
3 |
k |
6 |
|
3 |
k |
4 |
|
|||||||||||||||
t |
2 |
t |
2 |
t |
3 |
|
||||||||||||||||||||
s |
2*2 |
s |
2*2 |
s |
2*3* |
|
||||||||||||||||||||
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