Множество с заданным на нём отношением частичного порядка называется частично упорядоченным. Элемент частично упорядоченного множества называется минимальным, если во множестве нет элементов, меньших его.

Очевидно, что в примере 1 каждые два элемента множества {1, 2, 6,…} сравнимы между собою, а минимальным является 1. В примере 2 один идентификатор меньше другого, если тот образуется из него дописыванием символов в конце. Так, а меньше а1 и ааа, но а1 и аа несравнимы. Идентификатор а – минимальный. В примере 3 одно выражение меньше другого, если оно является его частью. Так, 1 и 2 меньше, чем (1)+(2), а (1)+(2) меньше, чем ((1)+(2))+(1); минимальными элементами являются все возможные константы, между собою несравнимые.

1.2. Рекурсивные подпрограммы

Рекурсия не является чем-то сверхсложным, а просто является ещё

одним способом программирования, которым можно пользоваться

успешно или злоупотреблять, как и всем остальным.

Д. Баррон

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

Пример 6

Напишем рекурсивную функцию f по такому определению функции факториал: n!=n*(n-1)! при n>1, 1!=1 (считается, что n>0).

function f(n:integer):integer;

begin

if n=1 then f:=1

else f:=n*f(n-1)

end;

При имитации выполнения вызовов рекурсивных подпрограмм их локальные переменные обозначают следующим образом. Если подпрограмма F вызвана из программы, то её локальная переменная Х обозначается F.X. При выполнении каждого рекурсивного вызова подпрограммы F, указанного в её теле, появляется новая переменная Х. Она обозначается добавлением префикса F. к обозначению переменной Х в предыдущем вызове: F.F.X, F.F.F.X и т.п.

Пример 7

Имитацию выполнения вызова f(2) функции из примера 6 можно представить в виде таблицы:

Пример 8

Наибольший общий делитель НОД(a, b) натуральных чисел a и b можно вычислить рекурсивно на основании таких равенств:

§ если b=0, то НОД(a, b)=a;

§ если а modb=0, то НОД(a, b)=b;

§ если а modb>0, то НОД(a, b)= НОД(b, а modb).

Этому определению соответствует следующая рекурсивная функция вычисления НОД:

function GCD(a, b:integer):integer;

(Greatest Common Divisor – Наибольший Общий Делитель)

begin

if b=0 then GCD:=a else

if a mod b=0 then GCD:=b

else GCD:=GCD(b, a mod b)

end;

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

Рассмотрим первое из них. В примере 6 приведена функция вычисления n!. Очевидно, что её вызов с аргументом, например 4, заканчивается лишь по окончании вызова с аргументом 3, а тот, в свою очередь, после вызова с аргументом 2 и т.д. Такие вызовы называются вложенными. Таким образом, вызов с аргументом 4 порождает ещё три вложенных вызова. Вообще, при вызове этой функции с аргументом n порождается ещё n-1 вызов, и общее количество незаконченных вызовов достигает n. Таким образом, глубиной рекурсии вызова подпрограммы называется максимальное количество незаконченных рекурсивных вызовов при выполнении её вызова.

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

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

Пример 9

По свойствам треугольника Паскаля, биномиальный коэффициент C(m, n)=1 при т<1 или n=0, или n=m; в противном случае C(m, n)= C(m­-1, n-1)+C(m-1, n).

В соответствии с этим равенством напишем рекурсивную функцию вычисления биномиального коэффициента C(m, n) по m, n, где 0<n<m:

function C(m, n:integer):integer;

begin

if (m<=1) or (n=0) or (n=m) then C:=1

else C:=C(m-1, n-1)+C(m-1, n)

end;

Как видим, каждый вызов, в котором значения аргументов m>1, 0<n<m, порождает два вложенных вызова. В результате происходит повторное вычисление одних и тех же величин. Например, выполнение вызова с аргументом (5,2) ведёт к тому, что вызов с аргументами (3,1) выполняется дважды, вызовы с аргументами (2,1), (1,0) и (1,1) – трижды, а общее количество вложенных вызовов достигает 18.

Нетрудно понять, что чем больше т и чем ближе n к т/2, тем большим будет общее количество вложенных вызовов. Мы не будем точно определять его зависимость от аргументов. Скажем лишь, что при n=m div2 или n=m div2+1 оно больше, чем 2т/2. Например, при т=60 это 230, или примерно 109. Если даже предположить, что за секунду можно выполнить 106 вызовов, то нужно больше 1000 секунд, т.е. более четверти часа. Однако нетрудно написать рекурсивную функцию, вызов которой с аргументом т порождает не более т/2 вложенных вызовов.