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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
В программировании рекурсия – это описание подпрограммы, содержащее
прямой или косвенный вызов этой подпрограммой самой себя. Если подпрограм-
ма
р вызывает себя в своем теле, то такая рекурсия называется прямой, если же
подпрограмма
р вызывает подпрограмму q, которая прямо или косвенно вызывает
р, то такая рекурсия называется косвенной. Рекурсией также называют процесс
выполнения рекурсивной подпрограммы.
2.2 Простые примеры использования рекурсии
Рассмотрим несколько примеров рекурсивных подпрограмм.
Пример 1.
procedure p;
begin
write(1);
p;
end;
При вызове процедуры
p произойдёт рекурсивное зацикливание: будет выво-
диться 1, после чего процедура снова будет вызывать себя и т.д. до бесконечно-
сти. Поскольку при каждом вызове процедуры на программный стек помещается
ее запись активации, то в конце концов программный стек переполнится, и про-
грамма завершится с ошибкой. Таким образом, чтобы рекурсия завершалась, не-
обходимо, чтобы рекурсивный вызов происходил не всегда, а лишь при выполне-
нии некоторого условия.
Пример 2.
procedure p(n: integer);
begin
write(n,' ');
if n>0 then p(n-1);
end;
При вызове p(5) вначале выведется 5, после чего вызовется p(4), выведет-
ся 4 и вызовется p(3) и т.д. до вызова p(0), который выведет 0 и, поскольку ус-
ловие n>0 станет ложным, рекурсия
завершится. Итак, в результате вызова p(5)
на экран будет выведено
5 4 3 2 1 0
Таким образом, использование рекурсии позволяет заменить цикл. Отметим,
что в простых примерах такая замена неэффективна, так как накладные расходы
на рекурсивный вызов процедур (копирование параметров на программный стек,
запоминание адреса возврата и т.д.) намного превосходят затраты на организацию
цикла
.

Страницы