Стили и методы программирования


Сети данных - часть 3


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

Теперь рассмотрим случай, когда рекурсивная реализация намного изящнее циклической, легче обобщается и не хуже по эффективности8)

Алгоритм Евклида

Рис. 14.1.3.  Алгоритм Евклида

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

function Euklides(n,m: integer) integer; { предполагаем m<=n} begin if n=m then resut:=n else result:=Euklides(n mod m, m); end;

Если пытаться вычислить наибольший общий делитель методом движения от данных к цели, то нам придется построить громадный массив значений НОД, лишь ничтожная часть значений в котором будет нужна для построения результата. Затраты на вычисление каждого отдельного элемента в данном случае малы, а при обратном направлении движения повторный счет не возникает.

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

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


Начало  Назад  Вперед