Читайте также:
|
“Обычная” рекурсия, при которой процедура или функция обращается к самой себе, называется “прямой рекурсией”. Существует также разновидность рекурсии, которую называют косвенной, или непрямой. Такой рекурсией является ситуация, когда процедура А вызывает себя в качестве вспомогательной не непосредственно, а через другую вспомогательную процедуру Б, которая, в свою очередь, обращается к процедуре А.
Косвенную рекурсию демонстрирует следующая программа, в которой находятся и выводятся все простые числа, не превышающие некоторого значения n.
Создадим функцию логического типа с именем Prim, проверяющую, является ли число i — ее параметр, простым. Чтобы ответить на этот вопрос, достаточно проверить делимость i на все простые числа, не превышающие квадратный корень из i. Перебор таких простых чисел можно организовать так: рассмотреть первое простое число — 2, а затем использовать функцию NextPrim, возвращающую следующее за значением ее параметра простое число:
Function Prim(j: word): boolean;
Var k: word;
Begin
k:= 2; {первое простое число}
While (k * k <= j) And (j mod k <> 0) Do k:= NextPrim(k);
{Значение k 'пробегает' последовательность простых чисел, начиная с 2 и до корня из j, при этом проверяется, делится ли j на одно из таких простых чисел}
If j mod k = 0
{Если встретилось составное число}
Then Prim:= false Else Prim:= true
End;
Функцию же NextPrim можно оформить так:
Function NextPrim(i: word): word;
Var p: word;
Begin
p:= i + 1;
While not(Prim(p)) Do p:= p + 1;
NextPrim:= p
End
В ней проверяются на “простоту” числа p, начиная со значения, на 1 большего значения параметра i, и делается это с помощью функции Prim (т.е. функция Prim вызывает функцию NextPrim, а последняя обращается к Prim, т.е. имеет место косвенная рекурсия).
При косвенной рекурсии возникает проблема — если первой описать функцию Prim, то она будет использовать еще не описанную функцию NextPrim, что в языке программирования Паскаль недопустимо (аналогично и если, наоборот, первой описать функцию NextPrim). Выходом является так называемое “опережающее описание” функции. Оно заключается в том, что заголовок одной из функций указывается первым со служебным словом Forward:
Function NextPrim(i: word): word; Forward;
— после чего полностью описывается вторая функция:
Function Prim(j: word): boolean;
Var k: word;
Begin
…
а затем — первая функция:
Function NextPrim;
Var p: word;
Begin
…
Обращаем внимание на то, что в полном описании функции NextPrim в заголовке список формальных параметров и тип результата не указываются (они уже объявлены ранее).
Заметим также, что число 2 — простое, а число 1 простым не считается. Это означает, что значение 2 в основной программе должно быть выведено без проверки, которая проводится с помощью функции Prim для всех нечетных чисел, не превышающих n.
5. Формы рекурсивных процедур 6
В общем случае любая рекурсивная процедура Р включает в себя некоторое множество операторов Д и один или несколько операторов рекурсивного вызова Р. Структура рекурсивных процедур может принимать три разных формы.
1. Форма с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате). Ее схема:
алг Р
нач
если <условие>
то
Р
все
Д
кон
или
алг Р
нач
если <условие>
то
Р
Д
все
кон
Примеры такой процедуры:
алг ВыводЧисла(арг цел n)
нач
если n > 1
то
ВыводЧисла(n — 1) все
вывод n, " "
кон
или
алг ВыводЧисла(арг цел n)
нач
если n > 0
то
ВыводЧисла(n — 1)
вывод n, " "
все
кон
Нетрудно предсказать результат их выполнения, например, при n = 5: 1 2 3 4 5.
2. Форма с выполнением действий до рекурсивного вызова (или с выполнением действий на рекурсивном спуске). Ее схема:
алг Р
нач
Д
если <условие>
то
Р
все
кон
или
алг Р
нач
если <условие>
то
Д
Р
все
кон
Примеры:
алг ВыводЧисла(арг цел n)
нач
вывод n, " "
если n > 1
то
ВыводЧисла(n — 1)
все
кон
или
алг ВыводЧисла(арг цел n)
нач
если n > 0
то
вывод n," "
ВыводЧисла(n — 1)
все
кон
Результат (при n = 5): 5 4 3 2 1.
3. Форма с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате). Ее схема:
алг Р
нач
Д
если <условие>
то
Р
все
Д
кон
или
алг Р
нач
если <условие>
то
Д
Р
Д
все
кон
Примеры:
алг ВыводЧисла(арг цел n)
нач
вывод n, " "
если n > 1
то
ВыводЧисла(n — 1)
все
вывод n, " "
кон
или
алг ВыводЧисла(арг цел n)
нач
если n > 0
то
вывод n, " "
ВыводЧисла(n — 1)
вывод n, " "
все
кон
Их результат: 5 4 3 2 1 1 2 3 4 5.
Дата добавления: 2015-02-16; просмотров: 262 | Поможем написать вашу работу | Нарушение авторских прав |