Глава 8. Как обойтись без рекурсии.

        Глава 8. Как обойтись без рекурсии.

     Для универсальных языков программирования (каковым является
паскаль)  рекурсия не дает ничего нового: для всякой рекурсивной
программы можно написать эквивалентную программу  без  рекурсии.
Мы  не будем доказывать этого, а продемонстрируем некоторые при-
емы, позволяющие избавиться от рекурсии в конкретных ситуациях.
     Зачем  это  нужно?  Ответ  прагматика мог бы быть таким: во
многих компьютерах (в том числе, к сожалению, и  в  современных,
использующих  так называемые RISC-процессоры), рекурсивные прог-
раммы в несколько раз  медленнее  соответствующих  нерекурсивных
программ.  Еще один возможный ответ: в некоторых языках програм-
мирования рекурсивные программы запрещены. А главное, при удале-
нии рекурсии возникают изящные и поучительные конструкции.

     8.1. Таблица значений (динамическое программирование)

     8.1.1. Следующая рекурсивная процедура вычисляет числа  со-
четаний  (биномиальные коэффициенты). Написать эквивалентную не-
рекурсивную программу.

        function C(n,k: integer):integer;
        | {n,k >=0; k <=n}
        begin
        | if (k = 0) or (k = n) then begin
        | | C:=1;
        | end else begin {0<k<n}
        | | C:= C(n-1,k-1)+C(n-1,k)
        | end;
        end;

Замечание. C(n,k) - число k-элементных подмножеств n-элементного
множества. Соотношение C(n,k) =  C(n-1,k-1)+C(n-1,k)  получится,
если  мы  фиксируем  некоторый элемент n-элементного множества и
отдельно подсчитаем  k-элементные  множества,  включающие  и  не
включающие этот элемент. Таблица значений C(n,k)

                        1
                      1   1
                    1   2   1
                  1   3   3   1
                .................

называется  треугольником  Паскаля  (того  самого). В нем каждый
элемент, кроме крайних единиц, равен сумме двух стоящих над ним.

     Решение. Можно воспользоваться формулой
        C(n,k) = n! / (k! * (n-k)!)
Мы, однако, не будем этого делать, так как хотим продемонстриро-
вать более общие приемы устранения  рекурсии.  Составим  таблицу
значений  функции  C(n,k), заполняя ее для n = 0, 1, 2,..., пока
не дойдем до интересующего нас элемента.

     8.1.2. Что можно сказать о времени работы рекурсивной и не-
рекурсивной версий в предыдущей задаче? Тот же вопрос о памяти.

     Решение. Таблица занимает место порядка n*n, его можно сок-
ратить до n, если заметить, что для вычисления следующей  строки
треугольника  Паскаля  нужна  только  предыдущая. Время работы в
обоих случаях порядка n*n.  Рекурсивная  программа  требует  су-
щественно большего времени: вызов C(n,k) сводится к двум вызовам
для C(n-1,..), те - к четырем вызовам для C(n-2,..) и т.д. Таким
образом, время оказывается экспоненциальным (порядка 2 в степени
n). Используемая рекурсивной версией память пропорциональна n  -
умножаем глубину рекурсии (n) на количество памяти, используемое
одним экземпляром процедуры (константа).

Кардинальный выигрыш во времени при переходе от рекурсивной вер-
сии к нерекурсивной связан с тем, что в рекурсивном варианте од-
ни  и  те  же  вычисления  происходят много раз. Например, вызов
C(5,3) в конечном счете порождает два вызова C(3,2):

                        C(5,3)
                       /     \
                     C(4,2)  C(4,3)
                    /  \     /   \
                 C(3,1) C(3,2)   C(3,3)
                ......................

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

     8.1.2. Порассуждать на ту же тему на примере рекурсивной  и
(простейшей)  нерекурсивной  программ для вычисления чисел Фибо-
наччи, заданных соотношением
        f(1) = f (2) = 1;  f(n) = f(n-1) + f(n-2) для n > 2.

     8.1.3. Дан выпуклый n-угольник (заданный координатами своих
вершин в порядке обхода). Его разрезают на треугольники диагона-
лями, для чего необходимо n-2 диагонали (докажите  индукцией  по
n). Стоимостью разрезания назовем сумму длин всех использованных
диагоналей.   Найти   минимальную  стоимость  разрезания.  Число
действий должно быть ограничено некоторым многочленом от n. (Пе-
ребор не подходит, так как число вариантов не ограничено многоч-
леном.)

     Решение. Будем считать, что вершины пронумерованы от 1 до n
и  идут  по  часовой стрелке. Пусть k, l - номера вершин, причем
l>k. Через A(k,l) обозначим многоугольник, отрезаемый от  нашего
хордой  k--l.  (Эта  хорда разрезает многоугольник на 2, один из
которых включает сторону 1--n; через A(k,l) мы  обозначаем  дру-
гой.)  Исходный многоугольник естественно обозначить A(1,n). При
l=k+1 получается "двуугольник" с совпадающими сторонами.









Через  a(k,l)  обозначим  стоимость  разрезания   многоугольника
A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу
для  a(k,l).  При  l=k+1  получается  двуугольник, и мы полагаем
a(k,l)=0. При l=k+2 получается треугольник, и в этом случае так-
же a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной  много-
угольника  A(k,l)  и,  следовательно,  стороной  одного  из тре-
угольников,  на  которые он разрезан. Противоположной вершиной i
этого треугольника может быть любая из вершин k+1,...,l-1, и ми-
нимальная стоимость разрезания может быть вычислена как

    min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)}

по всем i=k+1,..., i=l-1. При этом надо учесть,  что  при  i=k+1
хорда k--i - не хорда, а сторона, и ее длину надо считать равной
0 (по стороне разрез не проводится).

     Составив таблицу для a(k,l) и заполняя ее в порядке возрас-
тания числа вершин (равного l-k+2), мы получаем  программу,  ис-
пользующую память порядка n*n и время порядка n*n*n (однократное
применение  рекуррентной  формулы  требует выбора минимума из не
более чем n чисел).

     8.1.4. Матрицей размера m*n называется прямоугольная табли-
ца из m строк и n столбцов, заполненная числами. Матрицу размера
m*n  можно умножить на матрицу размера n*k (ширина левого сомно-
жителя  должна  равняться  высоте правого), и получается матрица
размером m*k. Ценой такого умножения будем считать  произведение
m*n*k (таково число умножений, которые нужно выполнить при стан-
дартном способе умножения - но сейчас это нам не важно). Умноже-
ние матриц ассоциативно, поэтому произведение n матриц можно вы-
числять в разном порядке. Для каждого порядка подсчитаем суммар-
ную цену всех матричных умножений. Найти минимальную цену вычис-
ления произведения, если известны  размеры  всех  матриц.  Число
действий должно быть ограничено многочленом от числа матриц.

     Пример.  Матрицы  размером  2*3, 3*4, 4*5 можно перемножать
двумя способами. В первом цена равна 2*3*4 + 2*4*5 = 24 +  40  =
64, во втором цена равна 3*4*5 + 2*3*5 = 90.

     Решение.  Представим  себе,  что первая матрица написана на
отрезке [0,1], вторая - на отрезке [1,2],..., s-ая - на  отрезке
[s-1,s]. Матрицы на отрезках [i-1,i] и [i,i+1] имеют общий  раз-
мер, позволяющих их перемножить. Обозначим его через d[i]. Таким
образом, исходным данным в задаче является массив d[0]..d[s].
     Через a(i,j) обозначим минимальную цену вычисления произве-
дения  матриц на участке [i,j] (при 0<=i<j<=s). Искомая величина
равна a(0,s). Величины a(i,i+1) равны нулю (матрица одна  и  пе-
ремножать ничего не надо). Рекуррентная формула будет такой:

    a(i,j) = min {a(i,k)+ a(k,j) + d[i]*d[k]*d[j]}

где  минимум берется по всем возможных местам последнего умноже-
ния, то есть по всем k=i+1..j-1. В самом деле, произведение мат-
риц на отрезке [i,k] есть матрица размера d[i]*d[k],  произведе-
ние  матриц  на отрезке [k,j] имеет размер d[k]*d[j], и цена вы-
числения их произведения равна d[i]*d[k]*d[j].

     Замечание. Две последние задачи похожи. Это сходство станет
яснее, если написать  матрицы  -  множители  на  сторонах  1--2,
2--3,..., s-1--s многоугольника, а на каждой хорде i--j написать
произведение всех матриц, стягиваемых этой хордой.

     8.1.5. Железная дорога с односторонним  движением  имеет  n
станций.  Известны цены белетов от i-ой станции до j-ой (при i <
j - в обратную сторонону проезда нет).  Найти  минимальную  сто-
имость  проезда  от начала до конца (с учетом возможной экономии
за счет пересадок).

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

     8.1.6.  Задано конечное множество с бинарной операцией (во-
обще говоря, не коммутативной и даже не ассоциативной).  Имеется
n  элементов  a[1]..a[n]  этого  множества и еще один элемент x.
Проверить,  можно  ли  так  расставить  скобки  в   произведении
a[1]..a[n],  чтобы  в  результате  получился  x.  Число операций
должно не превосходить C*n*n*n для некоторой константы C  (зави-
сищей от числа элементов в выбранном конечном множестве).

     Решение. Заполняем таблицу, в которой для  каждого  участка
a[i]..a[j]  нашего  произведения  хранится список всех возможных
его значений (при разной расстановке скобок).

     По существу этот же прием применяется в полиномиальном  ал-
горитме   проверки   принадлежности   слова  произвольному  кон-
текстно-свободному языку (см. главу 13).

     Следующая задача (задача о рюкзаке) уже упоминалась в главе
3 (Обход дерева).

     8.1.7.  Имеется  n  положительных  целых чисел x[1]..x[n] и
число N. Выяснить, можно ли получить N, складывая  некоторые  из
чисел x[1]..x[n]. Число действий должно быть порядка N*n.
     Указание. После i шагов хранится множество тех чисел на от-
реке   0..N,  которые  предствимы  в  виде  суммы  некоторых  из
x[1]..x[i].


     8.2. Стек отложенных заданий.

     Другой прием устранения рекурсии продемонстрируем на приме-
ре задачи о ханойских башнях.

     8.2.1. Написать нерекурсивную программу для нахождения пос-
ледовательности перемещений дисков в задаче о ханойских башнях.

     Решение. Вспомним рекурсивную программу:

    procedure move(i,m,n: integer);
    | var s: integer;
    begin
    | if i = 1 then begin
    | | writeln ('сделать ход', m, '->', n);
    | end else begin
    | | s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
    | | move (i-1, m, s);
    | | writeln ('сделать ход', m, '->', n);
    | | move (i-1, s, n);
    | end;
    end;

Видно, что задача "переложить i верхних дисков с m-го стержня на
n-ый"  сводится  к трем задачам того же типа: двум задачам с i-1
дисками и к одной задаче с единственным диском. Выполняя эти за-
дачи, важно не позабыть, что еще осталось сделать.

     Для этой цели заведем стек отложенных  заданий,  элементами
которого будут тройки <i,m,n>. Каждая такая тройка интерпретиру-
ется  как  заказ  "переложить i верхних дисков с m-го стержня на
n-ый". Заказы упорядочены в соответствии с требуемым порядком их
выполнения: самый срочный - вершина стека. Получам  такую  прог-
рамму:

    procedure move(i,m,n: integer);
    begin
    | сделать стек заказов пустым
    | положить в стек тройку <i,m,n>
    | {инвариант: осталось выполнить заказы в стеке}
    | while стек непуст do begin
    | | удалить верхний элемент, переложив его в <j,p,q>
    | | if j = 1 then begin
    | | | writeln ('сделать ход', p, '->', q);
    | | end else begin
    | | | s:=6-p-q;
    | | |      {s - третий стержень: сумма номеров равна 6}
    | | | положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s>
    | | end;
    | end;
    end;

(Заметим,  что  сначала в стек кладется тройка, которую надо вы-
полнять последней.) Стек троек может быть  реализован  как  стри
отдельных  стека.  (Кроме  того, в паскале есть специальный тип,
называемый "запись", который может быть применен.)

     8.2.2. (Сообщил А.К.Звонкин со ссылкой на Анджея  Лисовско-
го.)  Для  задачи  о ханойских башнях есть и другие нерекусивные
алгоритмы. Вот один из них: простаивающим стержнем  (не  тем,  с
которого  переносят, и не тем, на который переносят) должны быть
все стержни по очереди. Другое  правило:  поочередно  перемещать
наименьшее кольцо и не наименьшее кольцо, причем наименьшее - по
кругу.

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

     Решение. Цифры добываются с конца и закладываются в стек, а
затем печатаются в обратном порядке.

     8.2.4. Написать  нерекурсивную  программу,  печатающую  все
вершины двоичного дерева.

     Решение. В этом случае стек отложенных заданий будет содер-
жать  заказы двух сортов: заказ напечатать (в свое время) данную
вершину и заказ напечатать все вершины поддерева с данным корнем
(при этом nil считается корнем пустого дерева).  Таким  образом,
элемент стека есть пара: <тип заказа, номер вершины>.
     Вынимая элемент из стека, мы либо сразу исполняем его (если
это  заказ первого типа) либо помещаем в стек три порожденных им
заказа - в одном из шести возможных порядков.

     8.2.5. Что изменится, если требуется  не  печатать  вершины
двоичного дерева, а подсчитать их количество?

     Решение.  Печатание  вершины  следует заменить прибавлением
единицы к счетчику. Другими  словами,  инвариант  таков:  (общее
число  вершин)  = (счетчик) + (сумма чисел вершин в поддеревьях,
корни которых лежат в стеке).

     8.2.6. Для некоторых из шести возможных  порядков  возможны
упрощения, делающие ненужным хранение в стеке элементов двух ви-
дов. Указать некоторые из них.

     Решение. Если требуемый порядок таков:
        корень, левое поддерево, правое поддерево,
то  заказ  на печатание корня можно не закладывать в стек, а вы-
полнять сразу.
     Несколько более сложная конструкция применима для порядка
        левое поддерево, корень, правое поддерево.
В этом случае все заказы в стеке, кроме самого первого  (напеча-
тать поддерево) делятся на пары:
    напечатать вершину x, напечатать правое поддерево x
(т.е.  поддерево с корнем в правом сыне x). Объединив эти пары в
заказы специального вида и введя переменную для отдельного  хра-
нения первого заказа, мы обойдемся стеком однотипных заказов.
     То же самое, разумеется, верно, если поменять местами левое
и правое - получается еще два порядка.

     Замечание. Другую программу печати всех вершин дерева можно
построить на основе программы обхода дерева, разобранной в соот-
ветствующей  главе.  Там  используется команда "вниз". Поскольку
теперешнее представление дерева с помощью массивов l и r не поз-
воляет  найти  предка  заданной вершины, придется хранить список
всех вершин на пути от корня к  текущей  вершине.  Cмотри  также
главу об алгоритмах на графах.

     8.2.7.  Написать  нерекурсивный  вариант  программы быстрой
сортировки. Как обойтись  стеком,  глубина  которого  ограничена
C*log n, где n - число сортируемых элементов?

     Решение.  В  стек кладутся пары <i,j>, интерпретируемые как
отложенные задания на сортировку соответствующих участков масси-
ва. Все эти заказы не пересекаются, поэтому размер стека не  мо-
жет  превысить n. Чтобы ограничиться стеком логарифмической глу-
бины, будем придерживаться такого правила: глубже в  стек  поме-
щать больший из возникающих двух заказов. Пусть  f(n)  -  макси-
мальная  глубина стека, которая может встретиться при сортировке
массива из не более чем n элементов таким способом. Оценим  f(n)
сверху таким способом: после разбиения массива на два участка мы
сначала сортируем более короткий (храня в стеке про запас) более
длинный, при этом глубина стека не больше f(n/2)+1, затем сорти-
руем более длинный, так что

      f(n) <= max (f(n/2)+1, f(n-1)),

откуда очевидной индукцией получаем f(n) = O(log n).

     8.3. Более сложные случаи рекурсии.

     Пусть функция f с натуральными аргументами и значениями оп-
ределена рекурсивно условиями
        f(0) = a,
        f(x) = h(x, f(l(x))),
где a - некоторое число, а h и l -  известные  функции.  Другими
словами,  значение функции f в точке x выражается через значение
f в точке l(x). При этом предполагается, что для любого x в пос-
ледовательности
        x, l(x), l(l(x)),...
рано или поздно встретится 0.
     Если  дополнительно  известно,  что l(x) < x для всех x, то
вычисление f не представляет  труда:  вычисляем  последовательно
f(0), f(1), f(2),...

     8.3.1.  Написать  нерекурсивную  программу вычисления f для
общего случая.

     Решение. Для вычисления f(x) вычисляем последовательность
        l(x), l(l(x)), l(l(l(x))),...
до появления нуля и запоминаем ее, а затем вычисляем значения  f
в точках этой последовательности, идя справа налево.

     Еще более сложный случай из следующей задачи вряд ли встре-
тится  на  практике  (а  если  и встретися, то проще рекурсию не
устранять, а оставить). Но тем не менее: пусть функция f с нату-
ральными аргументами и значениями определяется соотношениями
        f(0) = a,
        f(x) = h(x, f(l(x)), f(r(x))),
где a - некоторое число, а l, r и h - известные функции. Предпо-
лагается, что если взять произвольное число и начать применять к
нему функции l и r в произвольном порядке, то  рано  или  поздно
получится 0.

     8.3.2. Написать нерекурсивную программу вычисления f.

     Решение. Можно было бы сначала построить дерево, у которого
в корне находится x, а в сыновьях вершины i стоят l(i) и r(i)  -
если только i не равно нулю, а затем вычислять значения функции,
идя от листьев к корню. Однако есть и другой способ.

     "Обратной польской записью" (или "постфиксной записью") вы-
ражения  называют  запись,  где знак функции стоит после всех ее
аргументов, а скобки не используются. Вот несколько примеров:

          f(2)                  2 f
          f(g(2))               2 g f
          s(2,t(7))             2 7 t s
          s(2, u(2, s(5,3))     2 2 5 3 s u s

Постфиксная  запись  выражения  позволяет удобно вычислять его с
помощью "стекового калькулятора". Этот калькулятор  имеет  стек,
который  мы  будем представлять себе расположенным горизонтально
(числа вынимаются и кладутся справа). При нажатии на  клавишу  с
числом  это число кладется в стек. При нажатии на функциональную
клавишу соответствующая функция применяется к  нескольким  аргу-
ментам у вершины стека. Например, если в стеке были числа
        2 3 4 5 6
и  нажата  функциональная клавиша s, соотвтетствующая функции от
двух аргументов, то в стеке окажутся числа
        2 3 4 s(5,6)

Перейдем теперь к нашей задаче. В процессе  вычисления  значения
функции  f мы будем работать со стеком чисел, а также с последо-
вательностью чисел и символов "f", "l", "r", "h", которую мы бу-
дем интерпретировать как последовательность  нажатий  кнопок  на
стековом калькуляторе.  Инвариант такой:

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

Пусть нам требуется вычислить значение, к примеру, f(100). Тогда
вначале мы помещаем в стек число 100, а  последовательность  со-
держит  единственный  символ "f". (При этом инвариант соблюдает-
ся.) Далее с последовательностью и стеком выполняются такие пре-
образования:


 старый       старая           новый       новая
 стек      последовательность  стек    последовательность

  X          x P               X x           P
  X x        l P               X l(x)        P
  X x        r P               X r(x)        P
  X x y z    h P               X h(x,y,z)    P
  X 0        f P               X a           P
  X x        f P               X             x x l f x r f h P

Обозначения: x, y, z,.. - числа, X - последовательность чисел, P
- последовательность чисел и символов "f", "l", "r", "h". В пос-
ледней строке предполагается, что m не равно 0. Эта строка соот-
ветствует равенству

        f(x) = h(x, f(l(x)), f(r(x))),

Эти  преобразования выполняются, пока последовательность не ста-
нет пуста. В этот момент в стеке  окажется  единственное  число,
которое и будет ответом.

     Замечание.  Последовательность по существу представляет со-
бой стек отложенных заданий (вершина которого находится слева).