Основы программирования. Файлы. Рекурсия - 25 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

27
Замечание 3. Можно доказать, что любая прямая рекурсия может быть заме-
нена итерацией.
2.3 Доказательство завершимости рекурсии
Как показать, что при вызове пряморекурсивной подпрограммы не происхо-
дит рекурсивного зацикливания, то есть рекурсивный вызов завершим? В самом
простом случае с каждым рекурсивным вызовом связывается целое число
n.
Предположим, что рекурсия завершается, когда
0
≤
n . Если нам удастся показать,
что при каждом рекурсивном вызове
n уменьшается, то рекурсивный вызов за-
вершим. Именно поэтому в большинстве рекурсивных подпрограмм удобно ис-
пользовать целый параметр
n, который при каждом рекурсивном вызове умень-
шается на 1, и завершать рекурсию, когда данный параметр становится равным 0.
2.4 Формы рекурсивных подпрограмм
Выделим следующие виды пряморекурсивных подпрограмм.
1) Действия осуществляется на рекурсивном спуске.
procedure p(n);
begin
S(n);
if B(n) then p(n-1)
end;
2) Действия осуществляются на рекурсивном возврате.
procedure p(n);
begin
if B(n) then p(n-1)
S(n); // отложенные действия
end;
3) Действия осуществляются и на рекурсивном спуске, и на рекурсивном
возврате.
procedure p(n);
begin
S1(n);
if B(n) then p(n-1)
S2(n);
end;
Данный вид рекурсии удобно представлять себе
следующим образом. Мы
спускаемся по лестнице с пронумерованными ступеньками (
n – номер ступеньки),
делая шаг на каждую ступеньку, пока выполняется условие
B(n), после чего воз-
вращаемся в начальную точку. Перед тем, как совершить следующий шаг, мы вы-
полняем действие
S1(n) и обязуемся выполнить действие S2(n) когда будем воз-

Страницы