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, и в это описании уже можно не указывать объявленные ранее формальные параметры.