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

Рекурсивные алгоритмы наиболее пригодны в случаях, когда представленная задача или используемые данные определены рекурсивно. Но это не значит, что при наличии таких рекурсивных определений лучшим способом решения задачи непременно является рекурсивный алгоритм. В действительности из-за того, что обычно понятие рекурсивных алгоритмов объяснялось на неподходящих примерах, в основном и возникло широко распространенное предубеждение против использования рекурсии в программировании и приравнивание ее к неэффективности. Повлиял на это и тот факт, что широко распространенный язык программирования Фортран запрещает рекурсивное использование программ и тем самым не допускает рекурсию, даже когда ее применение оправдано.

Программы, в которых следует избегать использования рекурсии, можно охарактеризовать следующей схемой, изображающей их строение. Эта схема (4.6) и эквивалентная ей (4.7):

P º if B then (S;P) (4.6)

P º (S; if B then P) (4.7)

Эти схемы естественно применять в тех случаях, когда выполняемые значения определяются с помощью простых рекуррентных соотношений. Рассмотрим, например, широко известный пример вычислений факториалов f_i = i!:

i =	0,	1,	2,	3,	4,	5,	...
fi =	1,	1,	2,	6,	24,	120,	…

(4.8)

«Нулевое» число определяется явным образом как f₀ = 1, а последующие числа обычно определяются рекурсивно - с помощью предшествующего значения:

f_i+1 = (i+1)∙f_i (4.9)

Эта формула предполагает использование рекурсивного алгоритма для вычисления п -го факториального числа. Если мы введем две переменные I и F для значений i и f_i на i -м уровне рекурсии, то увидим, что для перехода к следующему числу в последовательности (4.8) необходимы следующие вычисления:

I:= I + 1; F:= I * F (4.10)

и, подставив (4.10) вместо S в (4.6), мы получаем рекурсивную программу

P º if I < n then (I:= I+1; F:= I * F;P)

I:=0; F:= 1; P (4.11)

Первую строку в (4.11) можно записать на языке программирования Turbo Pascal следующим образом:

procedure P;

begin if I < n then

begin I:= I+1; F:= I*F; P (4.12)

End

End

Чаще употребляемая, но эквивалентная, по существу, форма дана в (4.13). Вместо процедуры здесь вводится функция. Функцию можно использовать непосредственно как элемент выражения. Тем самым переменная F становится излишней, а роль I выполняет явный параметр функции.

 

function F(I: integer):integer;

begin if I > 0 then F:= I*F(I - 1)

else F:= 1; (4.13)

end;

 

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

 

program factor;

Var

I: integer;

function F (I: integer): integer;

Begin

if I =0 then F:=1

else F:= I *(F (I -1));

end;

Begin { of main }

writeln ('Введите число '); readln (I);

writeln (I,'! = ', F (I));

readln;

end.

Программа 4.1.

Результат работы программы 1:

Введите число

7!=5040

 

Совершенно ясно, что здесь рекурсию можно заменить обычной итерацией, а именно:

I:= 0: F:= 1;

while I < n do

begin

I:= I + 1; (4.14)

F:= I * F

end

 

В общем виде программы, соответствующие схемам (4.6) или (4.7), нужно преобразовать так, чтобы они соответствовали схеме (4.15):

P º (x:= x₀; while B do S) (4.15)

 

Есть и другие, более сложные рекурсивные схемы, которые можно и должно переводить в итеративную форму. Примером служит вычисление чисел Фибоначчи, определяемых с помощью рекуррентного соотношения

fib_n+1 = fib_n + fib_n-1 для n > 0

и fib₁ = 1, fib₀ = 0. (4.16)

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Числа Фибоначчи играют важную роль в технике и даже в биологии (в соответствии с законом Фибоначчи растет численность живых организмов).

При непосредственном, «лобовом» подходе мы получим программу

function Fib(n: integer): integer;

begin if n = 0 then Fib:= 0 else

if n = 1 then Fib:= 1 else (4.17)

Fib:= Fib(n-1) + Fib(n-2)

End

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

program factor;

var i,n,fact: integer;

function Fib (n: integer): integer;

Begin

if n=0 then Fib:=0 else

if n=1 then Fib:=1 else Fib:= Fib (n-1)+ Fib (n -2);

end;

Begin { of main }

for i:=1 to 10 do writeln (i,' ', Fib (I),' ', i +10,' ',Fib(i +10)); readln;

end.

Программа 2

Результат работы программы 2:

1 1 11 89
2 1 12 144
3 2 13 233
4 3 14 377
5 5 15 610
6 8 16 987
7 13 17 1597
8 21 18 2584
9 34 19 4181
10 55 20 6765

Проследим, например, как работает рекурсивная функция при вычислении пятого члена ряда Фибоначчи. Для пятого члена значение функции должно равняться сумме четвертого и третьего членов. При вычислении четвертого члена функция обратиться к третьему и второму, при вычислении третьего – ко второму и первому, которые равны единице. Подобное «погружение» произойдет и при вычислении третьего члена как слагаемого четвертого (рис.1).

 

 

Рис.1. 15 вызовов Fib (n) при n =5

 

То есть мы видим, что в данном случае применение рекурсии на редкость неэффективно, мы заставляем процессор совершать множество «движений», причем их количество лавинообразно (экспоненциально) растет с ростом номера числа в ряду. Если первые десять чисел появляются на экране моментально, следующие с видимой и растущей задержкой, двадцатое на Pentium’e III (700МГц, 64МБ ОЗУ) «пережевывалось» около 5 секунд. (Сороковое – около минуты.)

Однако очевидно, что числа Фибоначчи можно вычислять по итеративной схеме, при которой использование вспомогательных переменных x = fib_i и y = fib_i-1 позволяет избежать повторного вычисления одних и тех же значений:

{ вычисление x = fib_n для n > 0}

i:= 1; x:= 1; y:= 0;

while i < n do

begin z:= x; i:= i + 1; (4.18)

x:= x + y; y:= z;

End

Заметим, что три присваивания x, y и z можно выразить всего лишь двумя присваиваниями без использования вспомогательных переменных z:

x:= x + y; y:= x – y

Итак, вывод таков: следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи. (Итерация -- способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ).

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

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

 

 

Лекция № 5.

Тема: Алгоритмы с возвратом

Основные вопросы, рассматриваемые на лекции:

1. Искусственный интеллект
2. Задача о ходе коня
3. Задача о восьми ферзях

Содержание лекционного материала

 

Искуственный интеллект

Особенно интересный раздел программирования — это задачи из области «искусственного интеллекта». Здесь нужно строить алгоритмы, которые находят решение определенной задачи не по фиксированным правилам вычисления, а мето­дом проб и ошибок. Обычно процесс проб и ошибок разде­ляется на отдельные подзадачи. Часто эти подзадачи наибо­лее естественно описываются с помощью рекурсии. Процесс проб и ошибок можно рассматривать в общем виде как поис­ковый процесс, который постепенно строит и просматривает (а также обрезает) дерево подзадач. Во многих случаях та­кие деревья поиска растут очень быстро в зависимости от заданного параметра. Соответ­ственно увеличивается стоимость поиска. Часто дерево по­иска можно обрезать, используя только эвристические сооб­ражения, и тем самым сводить количество вычислений к разумным пределам.

В этой лекции рассмотрим общий принцип разбиения таких задач на подзадачи и использование в них рекурсии.

ЗАДАЧА О ХОДЕ КОНЯ

Дана доска n x n, содержащая n ² полей. Конь, который ходит согласно шахматным правилам, помещается на поле с начальными координатами х ₀, у ₀. Нужно покрыть всю доску ходами коня, т. е. вычислить обход доски, если он суще­ствует, из n ² — 1 ходов, такой, что каждое поле посещается ровно один раз.

Очевидно, что задачу покрытия n ² полей можно свести к более простой: или выполнить очередной ход, или установить, что никакой ход невозможен. Поэтому будем строить алгоритм, который пытается сделать очередной ход.

Первая попытка выглядит так:

Begin инициация выборки ходов;

Repeat выбор следующего возможного хода из списка очередных ходов;

If он приемлем then

Begin запись хода;

If доска не заполнена then ( 5.1)

Begin попытка следующего хода;

If неудача then стирание предыдущего хода

End

End

Until (ход был удачным) или (нет других возможных ходов)

End

 

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

Type index =1.. n;

Var h: array [ index, index ] of integer

Так как нужно сохранять историю последовательного «за­хвата» доски, то необходимо представлять каждое поле доски целым числом, а не булевским значением, которое отражало бы просто факт занятия поля. Очевидно, можно остановиться на таких соглашениях:

h [ x, y ]=0: поле [ x, y ]не посещалось,

h [ x, y ]= i: поле [ x,y ] посещалось на i -м ходу (i <= 1 <= n ²).

Теперь необходимо выбрать соответствующие параметры. Они должны определять начальные условия следующего хода, а также сообщать о его удаче или неудаче. Первая задача вы­полняется заданием координат поля х, у, с которого делается ход, а также номером хода i (для его фиксации). Для реше­ния второй задачи нужен булевский параметр-результат: q = true означает удачу, q = false — неудачу.

Какие операторы можно теперь уточнить на основе этих решений? Разумеется, «доска не заполнена» можно выразить как «i < n ²». Кроме того, если ввести две локальные пере­менные u и v для обозначения координат возможного хода, определяемых по правилам хода коня, то предикат «прием­лем» можно выразить как логическую конъюнкцию двух усло­вий: чтобы новое поле находилось на доске, т. е. 1 <= u <= n и 1 <= v <= n, и чтобы оно ранее не посещалось, т. е. h [ u, h ]= 0. Фиксация допустимого хода выполняется с помощью присваивания h [ u, v ]: = i, а отмена хода (стирание)—как h [ u, v ]:=0. Если при рекурсивном вызове этого алгоритма в качестве параметра-результата передается локальная пе­ременная q 1, то вместо «ход был удачным» можно подставить q 1. Таким образом, мы приходим к программе:

Procedure try (i: integer; x, y: index, var q: Boolean);

Vaг v, u: integer;

ql: Boolean;

Begin инициация выбора ходов;

Repeat пусть u, v — координаты следующего хода, определяемого шахматными правилами;

If (1<=u<=n) and (l<=v<=n) and (h [u, v]=0) then

Begin h [u, v]: = i;

If i < sqr (n) then

Begin try (i+1,u, v, ql);

If not ql then h [u, v]: =0 (5.2)

End else q1: = true

End

Until ql or (нет других ходов);

q: =ql

End

 

Еще один этап уточнения, и можно будет написать программу уже полностью на нашем языке программирования. Надо заметить, что до сих пор программа разрабатывалась совершенно независимо от правил хода коня. Теперь пора обратить на них внимание. Если задана начальная пара координат (x, у), то имеется восемь возможных координат < u, v > следующего хода. На рис.5.1 они пронумерованы от 1 до 8.

 

Рис. 5.1. Восемь возможных ходов коня

Получать u, v из х, у просто — будем прибавлять к ним разности координат, помещенные либо в массиве пар раз­ностей, либо в двух массивах отдельных разностей. Пусть эти массивы обозначены через а и b и соответствующим об­разом инициированы. Для нумерации следующего возмож­ного хода можно использовать индекс k. Подробности пока­заны в программе ниже. Рекурсивная процедура вызывается в первый раз с параметрами х₀, у₀ — координатами поля, с которого начинается обход. Этому полю присваивается зна­чение 1, остальные поля маркируются как свободные:

h [ х ₀, у ₀]: = 1;

try (2, х ₀, у ₀, q)

Не следует упускать еще одну деталь. Переменная h [ u, v ] существует лишь в том случае, когда u и v находятся внут­ри границ массива 1.. n. Следовательно, выражение в (5.2), подставленное вместо «он приемлем» в (5.1), осмыс­ленно, только если его первые две составляющие истинны. В программе 5.1 это условие подходящим образом перефор­мулировано, кроме того, двойное отношение 1 <= u <= n заме­нено выражением u in [1,2,..., n ], которое при достаточно малых n обычно бывает более эффективным. В таблице 5.1 приведены решения, полученные при исходных позициях <1,1>, <3,3> для n = 5 и <1,1> для n = 6.

Параметр-результат q и локальную переменную q 1 можно заменить глобальной переменной и тем самым несколько упростить программу.

 

Program Knighstour;

Const n= 5; nsq = 25;

Type index =1.. n;

Vаг i, j: index;

q: Boolean',

s: set of index;

a,b: array [1.. 8] of integer;

h: array [index, index] of integer;

Procedure try (i: integer; x, y: index; Var ql: Boolean);

Var k,u,v. integer; ql: Boolean;

Begin

k:= 0;

Repeat

k:= k+l; ql:= false;

u:=x + a[k]; v:=у + b[k];

If (u in s) and (v in s) then

If h [u, v] =. 0 then

Begin h [u, v]: = i;

If i < nsq then

Begin try (i+l, u, v, q1);

If not ql then h [u, v]: = 0

End else ql: = true

End

Until ql or (k=8);

q:= ql

End {try};

Begin

s:= [1,2,3,4,5];

a[l]:= 2; b[l]:= 1;

а[2]:=1; b[2]:=2;

а[3]:=-1; b[3]:=2;

а[4]:=-2; b[4]:=1;

а[5]:=-2; b[5]:=-1;

а[6]:=-1; b[6]:=-2;

а[7]:=1; b[7]:=-2;

а[8]:=2; b[8]:=-1;

For i: =1 to n do

For j: = 1 to n do h [i, j]: = 0;

h[1,1]: = 1; try(2,l,1,q);

If q then

For i: = 1 to n do

Begin for j: = 1 to n do write (h [i, j]: 5);

Writeln;

End

Else writeln('Нет решения ')

End.

 

Программа 5.1. Ход коня

 

 

Таблица 5.1. Три обхода конем

 

 

 

 

 

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

Характерная черта этого алгоритма состоит в том, что он предпринимает какие-то шаги по направлению к общему решению, эти шаги фик­сируются (записываются), но можно возвращаться обратно и стирать записи, если оказывается, что шаг не приводит к решению, а заводит в «тупик». Такое действие называется возвратом. Из схемы (5.1) можно вывести общую схему (5.3), если предположить, что число возможных дальней­ших путей на каждом шаге конечно:

Procedure try;

Begin инициировать выборку возможных шагов;

Repeat выбрать следующий шаг;

If приемлемо then

Begin записать его;

If решение неполно then

Begin попробовать очередной шаг;

If неудачно then стереть запись (5.3)

End

End

Until удача или больше нет путей

End

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

Если, кроме того, на каждом шаге число исследуемых дальнейших путей фиксировано, скажем равно m, то исполь­зуется схема (5.4), вызываемая оператором «try (l)»:

Procedure try (i: integer);

Var k: integer;

Begin

k: =0;

Repeat

k: = k+1; выбрать k-й возможный путь;

If приемлемо then

Begin записать его; (5.4)

If i < n then

Begin try (i + 1);

If неудачно then стереть запись

End

End

Until удачно или (k = m)

End