В приведенной программе использована последовательность
2.3. Пример
В ¬2.2 мы описали взаимодействие N процессов. В приведенной программе использована последовательность вертикальных точек между скобками "parbegin" и "parend", что является лишь нестрогим формализмом для изображения совокупности N взаимодействующих последовательных процессов, при условии что N задано заранее. Эта общая форма может быть развернута для 3, 4 или 5071 взаимодействующих процессов, но она не дает формального описания N взаимодействующих процессов в случае, когда N является параметром, т. е. она не справедлива для любого значения N.
Цель данного параграфа - кратко показать, как может помочь в данном случае понятие так называемой "рекурсивной процедуры" в АЛГОЛе.
Мы видели, как с помощью описаний, следующих за "begin", вводились и именовались простые переменные (перечислением их имен) и упорядоченные множества переменных (описание массива). С помощью так называемого "описания процедуры" мы можем определить и поименовать отдельное действие. Такое действие вызывается затем использованием его имени в качестве оператора; при этом задаются параметры, к которым требуется применить это действие.
Рассмотрим в качестве иллюстрации следующую программу:
begin integer a, b; procedure квадрат(u, v); integer u, v; begin u := v
v end; L: квадрат(а, 3); квадрат(b, а); квадрат(а, b); endВ первой строке программы описываются целые переменные "а" и "b". В следующей строке начинается описание процедуры, названной "квадрат", которая использует два параметра, являющихся простыми целочисленными переменными (а не, скажем, массивами). Эта строка называется "заголовком процедуры". Следующий далее оператор - так называемое "тело процедуры" - описывает само действие с именем "квадрат": присвоить первому параметру квадрат значения второго параметра (отметим, что скобки "begin . . . end" в третьей строке, вообще говоря, избыточны). Затем следует, снабженный меткой "L", первый выполняемый оператор программы.
До его выполнения значения переменных "а" и "b" не определены, после выполнения имеем "а = 9". После выполнения следующего оператора значение "b" становится равным "81", после выполнения последнего оператора получаем "а = 6561", а значение "b" по-прежнему равно "81".
В этом примере процедура послужила по существу средством сокращения записи, позволив избежать трехкратного включения "тела" в программу, хотя мы вполне могли бы написать:
begin integer a, b; L: а := 3
3; b := а а; а := b b endВ случае более сложного, чем в этом примере, тела длина программы значительно увеличилась бы.
Метод "подстановки вместо обращения к процедуре соответствующим образом преобразованного тела процедуры", однако, невозможен, если процедура является рекурсивной, т. е. сама может вызывать себя. Такая процедура действительно расширяет выразительную силу языка программирования.
Проиллюстрируем использование рекурсивной процедуры на простом примере. Общий наибольший делитель (ОНД) двух натуральных чисел определяется так:
- если числа равны, то ОНД равен этому общему значению;
- если числа не равны, то ОНД равен общему наибольшему делителю меньшего из исходных чисел и их разности.
Иначе говоря, если ОНД не определяется тривиально (первый случай), то задача его нахождения заменяется отысканием ОНД для двух чисел с меньшими значениями.
(В следующей ниже программе спецификация "value v, w;" может быть пропущена читателем как не относящаяся по существу к обсуждаемому вопросу; она указывает, что для тела процедуры представляют интерес лишь числовые значения перечисленных параметров, задаваемые при обращении к процедуре).
begin integer a; procedure ОНД (u, v, w); value v, w; integer u, v, w; if v = w then u := v else begin if v < w then ОНД (u, v, w - v) else ОНД (u, v - w, w) end; ОНД (a, 12, 33) end
(B этом примере использована более сложная форма условного оператора, а именно:
if условие then оператор 1 else оператор 2
что означает: если "условие" удовлетворяется, то выполняется "оператор 1", а "оператор 2" пропускается; если "условие" не удовлетворяется, то пропускается "оператор 1", а выполняется "оператор 2".)
Читателю предоставляется проследить за последовательностью обращений к процедуре ОНД и убедиться, что переменная "а" получает значение "З". Необходимо также осознать, что (динамическая) схема обращений зависит от заданных параметров, и поэтому метод подстановки из предыдущего примера - замещение обращения к процедуре телом процедуры - привел бы здесь к трудностям.
Теперь мы составим программу умножения матрицы на вектор, в которой:
- порядок вычисления М произведений скаляра на скаляр точно определен (строки матрицы просматриваются слева направо);
- N строк матрицы могут обрабатываться параллельно. (Там, где мы не хотим ограничиваться только целочисленными значениями, использован описатель "real" вместо описателя "integer"; кроме того, мы ввели двумерный массив, что, вероятно, у читателя не вызовет затруднений.)
Предполагается, что перед входом в этот блок целые переменные "М" и "N" получают положительные значения.
begin real array матрица[1 : N, 1 : M]; real array вектор[1 : M]; real array произведение[1 : N]; procedure умножстроки(k); value k; integer k; begin if k > 0 then
parbegin
begin real s; integer j; s := 0; for j := 1 step 1 until M do
s := s + матрица[k, 3]
вектор[jl; произведение[k] := s end; умножстроки(k - 1) parendend; . . . . умножстроки(N); . . end
