Формы рекурсий

3.1. Простая линейная рекурсия

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

Пример 4. Нахождение наибольшего общего делителя (НОД) двух натуральных чисел по алгоритму Евклида. Алгоритм заключается в следующем: если m является точным делителем n, то НОД = m, в противном случае нужно брать функцию НОД от m и от остатка деления n на m.

{Линейная рекурсия}

{Алгоритм Евклида}

function NOD(n,m:byte):byte;

begin {NOD}

if m>n then NOD:=NOD(m,n) {Рекурсивная ветвь}

else if m=0 then NOD:=n {Терминальная ветвь}

else NOD:=NOD(m,n mod m) {Рекурсивная ветвь}

end; {NOD}

Первая рекурсивная ветвь в описании функции позволяет писать аргументы в любом порядке. В линейной рекурсии каждый рекурсивный вызов приводит непосредственно к одному дальнейшему рекурсивному вызову. Возникает простая линейная последовательность рекурсивных вызовов.

3.2. Параллельная рекурсия.

Если в описании подпрограммы, по меньшей мере, в одной рекурсивной ветви встречаются два или более рекурсивных вызовов, то говорят о нелинейной, или параллельной, рекурсии. Один из наиболее ярких примеров такой рекурсии дают числа Фибоначчи:

f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2).

Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов:

1 2 3 5 8 13 21 34 55 …

Пример 5. Вычислить n-й член ряда Фибоначчи.

{Параллельная рекурсия. Числа Фибоначчи}

function fib(n:integer):integer;

begin {fib}

if n=0 then fib:=0 {терминальная ветвь}

else if n=1 then fib:=1 {терминальная ветвь}

else fib:=fib(n-1)+fib(n-2) {рекурсивная ветвь}

end; {fib}

Для определения текущего значения f(n) функция fib вызывает себя в одной и той же рекурсивной ветви – параллельно. Заметим, что параллельность является лишь текстуальной, но никак не временной: вычисление ветвей в стеке производится последовательно. В отличие от линейной рекурсии, при которой структура рекурсивных вызовов линейна, нелинейная рекурсия ведет к древовидной структуре вызовов. Вызовы лавинообразно ведут к экспоненциальному нарастанию возникающих рекурсивных вызовов – «каскаду вызовов», отсюда еще одно название – каскадная рекурсия.

3.3. Взаимная рекурсия.

Если процедура или функция вызывает себя сама, это называют прямой рекурсией. Но может встретиться ситуация, когда подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой. В этом случае имеем дело с косвенной, или взаимной, рекурсией.

Пример 6. Программа выдает простые числа от 1 до n, для чего используются функции next и prim, которые вызываются перекрестно.

{Взаимная рекурсия. Простые числа}

program Primzahlen;

var n,i:integer;

{Опережающее описание}

function next(i:integer):integer; forward;

{prim определяет: j – простое число или нет}

function prim(j:integer):Boolean;

var k:integer;

begin {prim}

k:=2;

write(k*k<=j) and (j mod k<>0) do

k:=next(k); {prim вызывает next}

if j mod k=0 then prim:=false

else prim:=true

end;

{next вычисляет, каково следующее за j простое число}

{Параметры функции уже стоят в ссылке вперед}

function next;

var k:integer;

begin {next}

k:=i+1;

while not(prim(k)) do k:=k+1; {next вызывает, в свою очередь, prim}

next:=k;

end {next};

begin {primzahlen}

write(‘Введите положительное число n,’);

readln(n);

writeln(‘Предшествующие ему простые числа’);

for i:=2 to n do if prim(i) then write(i:6)

end. {primzahlen}

Функция prim определяет, является ли j простым числом, для этого просматриваются все простые числа начиная с двух, вплоть до корня из j, и проверяется, делится ли j на одно из таких простых чисел. Для поиска следующего простого числа используется функция next, которая, в свою очередь, для идентификации простых чисел использует функцию prim. Однако в Паскале любой идентификатор перед употреблением должен быть описан и при использовании подобных функций возникает проблема ссылок вперед. Для того чтобы такого рода вызовы стали возможны, вводится опережающее описание функции next, которое предшествует обращению к ней и состоит из ее заголовка с указанием директивы forward, заменяющей тело функции. Теперь в функции prim можно использовать обращение к next – ее формальные параметры уже известны и компилятор может правильно организовать ее вызов. Полное описание функции next помещается в программе после описания prim, и в это описании уже можно не указывать объявленные ранее формальные параметры.

3.4. Рекурсия более высокого порядка.

Используя более мощные виды рекурсии, можно записывать относительно лаконичными средствами и более сложные вычисления. Одновременно с этим, поскольку определения довольно абстрактны, растет сложность отладки и понимания программ.

Если в определении функции рекурсивный вызов является аргументом вызова этой же самой функции, то в такой рекурсии можно выделить различные порядки (order) в соответствии с тем, на каком уровне рекурсии находится вызов. Такую форму рекурсии называют рекурсией более высокого порядка. Функции, которые до сих пор определяли, были функциями с рекурсией нулевого порядка. В качестве классического примера рекурсии первого порядка часто приводится функция Аккермана:

A(m,n)=n+1 при m=0;

A(m,n)=A(m-1,1) при n=0;

A(m,n)=A(m-1,A(m,n-1)) в остальных случаях.

Кажущаяся простота этой функции обманчива. Вызов функции завершается всегда, однако ее вычисление довольно сложно, число рекурсивных вызовов растет лавинообразно уже при малых значениях аргумента.

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

Дата добавления: 2014-11-15; просмотров: 926; Нарушение авторских прав

Мы поможем в написании ваших работ!