Косвенная рекурсия

Еnd.

Begin

Begin

Begin

fact:=n;

for i:=n-1 downto 2 do

fact:=fact*i;

Fact1:= fact;

end;

№2 с рекурсией

Function Fact2(n:integer):longint;

if n=0 then Fact2:=1

else Fact2:=Fact2(n-1)*n;

end;

Если в основной программе обратиться к функции Fact2, например:

……………..

a:=Fact2(4);

……………..

то будут выполнены действия:

a:=Fact2(3)*4;

a:=Fact2(2)*3*4;

a:=Fact2(1)*2*3*4;

a:=Fact2(0)*1*2*3*4;

a:=1*1*2*3*4=24

Рекурсивный процесс закончен.

Здесь при каждом новом обращении к подпрограмме функции Fact2 фактические параметры, которые она использует, записываются в стек (Stack).

Структура типа LIFO

Параметры помещаются один за другим в стек и забираются в обратной последовательности. Рекурсия – это один из методов, который применяют, если необходимо выполнить повторные действия, таким образом, как видно из примеров, в этом случае можно действовать двумя способами:

1. с помощью цикла (пример Function Fact1).
2. с помощью рекурсии, т.е. вложения одной операции в другую (пример Function Fact2)

Примеры 1 и 2 демонстрируют, прежде всего, различие между циклом и рекурсией. Fact1 использует вспомогательную локальную переменную fact. Рекурсивная функция Fact2 обходится без вспомогательных переменных. Однако выполнение рекурсивных подпрограмм приводит к многократным обращениям к ним самим. Это увеличивает время выполнения. Кроме того, есть опасность переполнения стека, в котором записываются адреса возвратов из подпрограммы, а также размещаются значения фактических параметров. Поэтому использование рекурсивных подпрограмм с одной стороны сокращает запись программы, делая ее более понятной, а с другой стороны увеличивает затраты памяти и машинного времени.

Рекурсия называется прямой, если подпрограмма вызывает саму себя и косвенной, если две или более процедуры и функции вызывают друг друга взаимно.

1) 2)

Пример: Две процедуры вызывают друг друга взаимно.

Program primer;

………………….

procedure А1(k:integer);

Дата добавления: 2015-06-27