Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

465

(Здесь для простоты функция N! при неположительном целом аргументе до-

определена как единица).

Выполнение рекурсивных программ проще всего пояснить, отслеживая

процесс вычислений и сопоставляя его с процессом вычислений по итера-

тивной схеме. В рассматриваемом примере сопоставляются два способа вы-

числения N! при N, равном четырем.

По итеративной схеме произведение 1 ∗ 2 ∗ 3 ∗ 4 вычисляется путем на-

капливания его в переменной

инициализируется единицей, затем при

равном 2, 3, и 4, увеличивается, соответственно, в 2, 3, и 4 раза (после выпол-

нения оператора

F := F * I

), и, как следствие, становится равной 2, 6 и 24.

равное 4 — последнее значение, при котором перевычисляется

, и именно

при этом значении

формируется последнее

(равное 24), которое является

результатом выполнения итеративной программы.

По рекурсивной схеме 4! вычисляется как произведение 3! на 4. Если 3!

вычислено, то 4! есть результат умножения этого значения на 4. Таким обра-

зом, чтобы подсчитать 4! по рекурсивной схеме, надо сначала вычислить 3!,

что требует вычисления 2!, для которого требуется предварительно вычи-

слить 1!. Последнее, согласно алгоритму, есть 1, т. к. N , равное 1, меньше,

чем 2. 2! есть 1! (уже вычисленное и равное 1), умноженное на 2. 3! — это

произведение 2 ∗3, где 2 = 2! = (3 −1)!, а 3 — величина N, использованная

при вызове алгоритма для нахождения 3!. Наконец, коль скоро 3! получено,

можно продолжить вычисление 4! как 3! ∗ N при N = 4.

8.7.1. Сопоставление итеративной и рекурсивной схем

Главная цель сопоставления двух схем программирования заключается в

решении вопроса о том, когда в реальных программах использовать ту или

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

трансформацию в рекурсивный и наоборот с сохранением вычислительной

эквивалентности. Любое математическое утверждение об эквивалентности

или об изоморфизме структур не следует понимать буквально: будто бы вы-

бор схемы или структуры данных непринципиален. Как правило, трансфор-

мации, предоставляемые доказательством эквивалентности, могут оказаться

сложными, к тому же они никак не учитывают заботы о модифицируемости

и чаще всего абстрагируются от вопросов сложности вычислений. Поэтому

для практического программирования весьма важно знать теоретические ре-

зультаты об эквивалентности либо изоморфности, но интерпретировать их

466

ГЛАВА 8. ПОДПРОГРАММЫ

ст

оит как наличие нескольких альтернативных структур, выбор одной из ко-

торых нужно осуществить в соответствии с условием задачи.

Как правило, рекурсивные программы с точки зрения расхода времени и

памяти менее эффективны, чем итеративные: во-первых, каждое порожде-

ние экземпляра связано с отведением для него определенной памяти, а во-

вторых, алгоритмически обусловленное время вычислений увеличивается за

счет затрат на организацию вызова подпрограммы и возврата из нее, и хотя

некоторые вычислительные машины осуществляют эти действия на аппарат-

ном уровне (и как следствие, делают работу с подпрограммами оптималь-

ной), далеко не все архитектуры машин допускают такую поддержку проце-

дурного механизма.

Вместе с тем, рекурсивный алгоритм во многих случаях проще и нагляд-

нее, чем итеративный, особенно, когда имеется рекуррентное соотношение,

определяющее задачу (приведенный пример служит тому иллюстрацией).

Может оказаться, что задача рекурсивна по существу, т. е. для ее решения

удобнее всего воспользоваться алгоритмом с порождением вычислительных

процессов, подчиненных стековой дисциплине. Итеративное описание тако-

го алгоритма, как правило, будет завуалированной рекурсией, и потому ра-

зумно сразу же составлять рекурсивную программу.

Рекуррентные соотношения, определяющие функции, практически без

затруднений могут быть использованы при составлении рекурсивных про-

грамм.

Предупреждение

Буквальное следование рекуррентному определению почти все-

гда таит в себе опасность повторного счета и фантастической по-

тери эффективности вычислений.

Следующие примеры демонстрируют такую опасность.

Пример 8.7.1. Пусть требуется вычислить N-ое число Фибоначчи, опреде-

ляемое соотношением:

Φ(1) = Φ(2) = 1;

Φ(N) = Φ(N − 1) + Φ(N − 2), при N > 1.

Функцию

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

467

Программа 8.7.2

function F ( N : Integer ) : Integer;

begin

if N < 2

then F := 1

else F := F ( N - 1 ) + F ( N - 2 )

end;

заданную в точном соответствии с рекуррентным соотношением,нельзя при-

знать удовлетворительной.

В самом деле, вычисление

F(5)

требует вычислить

F(4)

F(3)

, которые

затем складываются. Каждое из них есть вызов

без передачи какой-либо

информации об истории вычислений. В результате

F(3)

считается дважды:

сначала в рамках вычисления

F(4)

, т. е. в первом аргументе выражения

F ( N

- 1 ) + F ( N - 2 )

, а затем повторно в ходе вычисления

F(5)

при вычислении

второго аргумента этого же выражения. В свою очередь,

F(2)

вычисляется

уже три раза: дважды при каждом вызове

F(3)

и еще один раз в ходе вы-

числения

F(4)

. Здесь повторный счет возник в связи с тем, что алгоритм не

предусматривает сохранения информации о ранее вычисленных значениях

F(K)

, 1 6 K < N.

Таким образом,вычисление чисел Фибоначчи,буквально следующее опре-

деляющему рекуррентному соотношению,приводит к неэффективности.Для

обучаемых рекомендуется выполнить упражнения 1–4.

Конец примера 8.7.1.

На примере функции

легко видеть, что в комплекте локальных данных под-

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

звана функция как первый или второй операнд сложения, требуется обеспе-

чить тот или иной корректный возврат при завершении экземпляра.

Пример 8.7.2. Вычисление наибольшего общего делителя (НОД) двух нео-

трицательных чисел. НОД(x, y) определяется как максимальное целое, ко-

торое делит без остатка x и y. Алгоритм основан на следующих свойствах

функции НОД:

НОД(x, x) = x;

НОД(x, y) = НОД(x, y − x), если y > x.

468

ГЛАВА 8. ПОДПРОГРАММЫ

Программа 8.7.3

procedure MCD (x,y : Integer 0..MAXINT; var R : Integer);

begin

if x = y

then R := x

else if x > y

then MCD ( y, x, R ) { * }

else MCD ( x, y - x, R )

end;

void MCD ( int x, y, *int R) {

if (x==y) &R = x;

else if (x>y) MCD (y, x, &R);

else MCD (x, y - x, &R);

}

Замечания к процедуре

MCD

1. Приведенный алгоритм содержит ошибку:при вызове процедуры с пер-

вым или вторым параметром, равным нулю, произойдет ‘бесконечное’

порождение экземпляров (почему?). Обучаемым предлагается испра-

вить программу,например,с учетом того,что для любого x НОД(0, x) =

НОД(x, 0) = x.

2. Программа может быть улучшена за счет замены оператора

MCD(y,x,R)

в строке

{ * }

на

MCD (y,x - y,R)

. Предлагается определить отличие двух

вариантов вычислений.

3. Для углубления понимания механизма рекурсии полезно проследить,

какие изменения процесса вычислений вызовет объявление

как

параметров-переменных.

4. Как вы думаете,почему в этой программе,внешне схожей с процедурой

вычисления чисел Фибоначчи, не происходит повторный счет?

Легко показать, что если некоторая функция для всех положительных целых

x и y обладает указанными свойствами, то она является функцией, вычисля-

ющей наибольший общий делитель двух чисел. Таким образом, с точностью

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

469

до ошибки, отмеченной в замечании 1, процедура

MCD

корректно решает за-

дачу.

Конец примера 8.7.2.

8.7.2. Рекурсия через параметры

Понятие рекурсивной процедуры возникает в связи с осуществимостью

и полезностью применения в практике программирования приема, когда в

ходе вычислений одновременно существует несколько экземпляров одной и

той же программной единицы (см. п. 8.4.3). Как правило, различаются явная

рекурсия — вызов процедуры в ней самой, и взаимная (опосредованная) ре-

курсия — в тексте программы представлена последовательность процедур,

вызывающих друг друга и в конечном итоге вызывающих первую из проце-

дур последовательности.

Отличительной особенностью всех таких случаев рекурсии является то,

что она всегда может быть выявлена путем анализа текстов самих подпро-

грамм. При взаимной рекурсии этот анализ довольно сложен, но, тем не ме-

нее, вполне осуществим (обучаемым предлагается построить соответствую-

щий алгоритм).

В практике программирования встречается еще один способ задания ре-

курсивных алгоритмов, который не всегда может распознаваться на основа-

нии только такой информации. Этот случай связан с заданием рекурсии че-

рез параметры. В языках со строгой типизацией (например, в

Pascal

, где для

повышения надежности программирования вводится ограничение: в параме-

трах-функциях и параметрах-процедурах не допускаются иные параметры,

кроме параметров, передаваемых по значению) такая рекурсия невозможна.

Но если соответствующие ограничения на параметризацию не накладывают-

ся, появляется возможность задавать процедуры, становящиеся рекурсивны-

ми через параметры.

Пусть, к примеру, описана процедура

с параметром-процедурой

procedure P ( procedure Q );

begin

...

Q(R);

{ В этой строке с точки зрения языка

Pascal

содержится }

{ошибка, т. к. в определении параметра

не указано, что им }

{является процедура с параметром }

...

end;

470

ГЛАВА 8. ПОДПРОГРАММЫ

Вызов такой процедуры корректен, если в качестве ее фактического пара-

метра используется процедура с параметром. В противном случае ошибочен

оператор

Q(R)

. Отсутствие в спецификации процедуры

информации о ви-

де возможных параметров параметра-процедуры

не позволяет контролиро-

вать, какие фактические параметры могут подставляться вместо формальной

процедуры

. В частности, оказывается допустимым оператор

P(S)

, если в

программе имеется описание

procedure S ( procedure T ); {

Как и в описании

P,}

{

здесь не специфицированы параметры

}

{

формальной процедуры

т. е. с точки

}

{

зрения языка

Pascal T

может вызываться

}

{

только без параметров

}

begin

...

end;

Если употребление оператора

P(S)

не приводит к опосредованной рекур-

сии

, то вычисление этого оператора не дает рекурсии. В то же время, сама

процедура

годится для использования в качестве своего фактического па-

раметра. Вызов

P(P)

формально не является ошибочным (в рамках сделан-

ных предположений, но не с точки зрения

Pascal

). Однако его вычисление

может привести к выполнению оператора

Q(R)

, где

— формальный пара-

метр-процедура, и, следовательно, к порождению еще одного экземпляра

до завершения выполнения предыдущего экземпляра, т. е. к рекурсии

. Та-

ким образом, в одном случае обращение к

является рекурсивным, а в дру-

гом — нет. И ситуации, когда

надо транслировать как рекурсивную, а когда

как нерекурсивную, не распознаваемы путем анализа текстов процедур.

Если процедуры,подобные

,предлагаются в качестве библиотечных, ко-

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

подпрограммы, то это может привести к существенной потере эффективно-

сти библиотеки. Следует отметить, что алгоритмы таких подпрограмм труд-

ны для понимания. Все это приводит к тому, что рекурсия через параметры

редко используется в практике программирования. Поэтому зачастую в язы-

ках не разрешается употреблять параметры-подпрограммы. Однако прямо-

линейные запреты средств такого рода затрудняют задание полезных алго-

ритмов, в которых желательно подключение внешних вычислений для вы-

полнения тех или иных действий (классический пример —вычисление опре-

деленных интегралов,когда подынтегральная функция является параметром).

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

471

Гибкий путь преодоления недостатков рекурсии через параметры — это бо-

лее глубокие спецификации параметров-подпрограмм, что и предлагается в

стандарте описания языка

Pascal

Может показаться, что при отсутствии спецификаций параметров для па-

раметров-подпрограмм повышается выразительность языка. Так, в этом слу-

чае для процедуры

procedure PS ( Npar : Integer; procedure T ); {

Это не Паскаль!

}

...

begin

...

case Npar of

0 : T;

1 : T ( x );

2 : T ( x, y );

end;

...

end; {PS}

в одной программе правомерны операторы

PS(0,PR0);PS(1,PR1);

PS(2,PR2);

где

PR0

PR1

PR2

— имена процедур с 0, 1 и 2 параметрами соответ-

ственно. Однако цена такой ‘выразительности’ чрезмерна: из-за нее исчезает

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

процедуре:

PS(0,PR1)

PS(2,PR1)

и др. Существеннее, что эта возможность

исключается и в более обычных ситуациях.

Для разработчиков различных языков цена ограничений, которые надо

вводить на параметризацию с целью повышения надежности, различна. До-

пускаемая ими свобода спецификации параметров колеблется от простого

обозначения и игнорирования возникающих трудностей (как в

Алголе 60

приведенной иллюстрации) до полного запрета употреблять параметры-под-

программы.

К примеру, способ введения параметров-процедур и параметров-функ-

ций в расширения языка

Pascal

(см. п. 8.5.5) может привести к рекурсии че-

рез параметры, которая, однако, кажется контролируемой, поскольку соот-

ветствующий программный тип с необходимостью должен быть определен

в описании типов рекурсивно. Пусть, к примеру:

type

fff =

function

( N : Integer; M : fff ) : Real;

472

ГЛАВА 8. ПОДПРОГРАММЫ

Здесь имя типа

fff

использовано для спецификации формального параметра

. Допустимые для

фактические параметры в силу определения

fff

должны

удовлетворять шаблону, введенному при описании

fff

. В результате функции

типа

fff

рекурсивны непосредственно или взаимно.

Правомерна,по крайней мере,формально, еще одна возможность,не при-

водящая к рекурсии: когда такая функция имеет фиктивный параметр, т. е. не

используемый в ее теле:

function mm ( X : Integer; M : fff ) : Real;

begin {

Параметр

не используется

}

mm := X - 1 {

в теле функции

mm. }

end;

Такая возможность, хотя и кажется избыточной, заслуживает отдельного

обсуждения. Рекурсия не может кончиться, если в конце концов мы не опи-

раемся на нечто, заранее заданное. Точно так же и с любыми другими индук-

тивными определениями. Так что при использовании рекурсии этот случай

должен быть обязательно предусмотрен.

8.7.3. Пример для самостоятельного анализа

В настоящем разделе приводится пример программы с рекурсивными про-

цедурами, который предлагается для самостоятельного анализа. Программа

предназначена для распечатки всех последовательностей, составляемых из

символов “1”, “2” и “3”, среди которых знаком “+” помечаются удовлетворя-

ющие некотрому условию, которое Вам предстоит выяснить самим.

Для решения задачи выбран рекурсивный алгоритм, но это не означает,

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

Программа 8.7.4

program SEQ;

const NN = 100;

K = 5;

Ms = ’3’;

MaxNstr = 23;

var i, N : Integer;

S : packed array [ 1 .. NN ] of Char;

sim: packed array [ 1 .. K ] of Char;

8.7. РЕКУРСИВНЫЕ ПРОГРАММЫ

473

M, Nseq, MaxNseq, Nstr : Integer;

procedure Init;

begin

for i := 1 to N do

S [i] := ’1’;

M := N;

end; { Init }

function Next : Boolean;

begin

if S [ M ] = Ms

then if M > 1

then begin

S [ M ] := ’1’;

M := M - 1; Next := Next; M := M + 1

end

else Next := false

else begin S [ M ] := Succ ( S [ M ] ); Next := true end

end; {Next }

procedure Inpt;

var ch : Char;

begin

Writeln ( ’Введите проверяемую строку’ );

N := 0;

repeat Read ( ch ); N := N + 1; S [ N ] := ch

until ( N >= NN ) or ( ch = #13 );

N := N - 1

end; { Inpt }

function Good1 ( ib, ie : Integer) : Boolean;

var i, l : Integer;

gl : Boolean;

function Eq ( i, j, l : Integer) : Boolean;

var imax : Integer;

r : Boolean;

begin

l := l - 1;

474

ГЛАВА 8. ПОДПРОГРАММЫ

imax := i + l;

r := ( l >= 0 ) and ( imax <= N ) and ( j + l <= N );

while r and ( i <= imax ) do

begin

r := S [i] = S [j];

i := i + 1; j := j + 1;

end;

Eq := r

end; { Eq }

begin

if ib + 1 = ie

then Good1 := TRUE

else if Good1 ( ib, ie - 1 )

then begin

gl := true; l := ( ie - ib ) div 2;

while gl and ( l > 0 ) do

begin

gl := not Eq ( ie-l-l, ie-l, l );

l := l - 1

end;

Good1 := gl

end

else Good1 := false

end; { Good1 }

begin {

Главная программа

}

Write (’Введите длину последовательностей ’ ); Readln ( N );

Init;

Nstr:= 0; Nseq := 0; MaxNseq := 80 div ( N + 2 );

repeat

if Good1 ( 1, N )

then Write (’+’)

else Write (’ ’);

for i := 1 to N do Write ( S [ i ] ); Write (’ ’);

Nseq := Nseq + 1;

if Nseq >= MaxNseq then begin

Nseq := 0; Nstr := Nstr + 1;

Writeln