Рекурсивные алгоритмы (преимущества и недостатки)

Дерево

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

На этой иллюстрации (см. рис 4) изображена структура бинарного дерева на связанной памяти, здесь К – корень; Л1,Л2,Л3 – «листья» – вершины с «пустыми» связями («не выросшими» поддеревьями).

                                                                               К

                                                                                                    

                                                                                                 Информационное поле

                                                                                                 Связь с левым потомком

                                                                                                 Связь с правым потомком    

 

 

 

                                      Л1                                           Л2                                           Л3

 

 

 

Рис. 4 Схема «Структура бинарного дерева»

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

Примером такого отношения может служить отношение «больше- меньше», определяющее структуру бинарного дихотомического дерева. В таком дереве все вершины любого правого поддерева имеют значение информационного поля большее, чем значение такого же поля у корня, а веpшины соответствующего левого поддерева – меньшее. Например, конструирование дихотомического дерева по последовательности целых чисел  30, 70, 80, 21, 25, 17, 4, начиная с 30,  должно приводить к созданию следующей структуры:

 

 

Рис. 5 Схема «Структура дихотомического дерева»

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

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

Например, в теории трансляции широко используется понятие Польской инверсной записи (ПОЛИЗ) – особой системы представления математических выражений символьными последовательностями. Так, например, выражение  «a + b * c» будет представлено в ПОЛИЗЕ строкой «a b c * +». Если представить исходное выражение в естественной иерархической форме бинарного дерева:

 

      

  

                   

Рис. 6 Схема «Иерархическая форма бинарного дерева»

то его восходящий обход (пунктир на рис. 6) приведет к строке « a b c * +», определяющей «польский» эквивалент исходной строки. Формула восходящего обхода «Левый–Правый–Корень» (ЛПК) определяет правило обхода бинарного дерева: восходящий обход связан с обходом его левого поддерева, затем правого поддерева, затем корня. Поскольку каждая вершина дерева может интерпретироваться как корень «вырастающего из нее» поддерева, это правило применяется рекурсивно к каждой вершине обходимого дерева. Правило ЛКП (Левый–Корень–Правый) определяет так называемый смешанный обход, правило КЛП – нисходящий обход и т.д. Нетрудно заметить, что смешанный обход дерева дихотомии по правилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ – к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, отношением порядка на множестве информационных компонент его вершин и видом обхода существует глубокая связь, определяемая рекурсивной природой структуры дерева. Рекурсивные процедуры обхода бинарных деревьев пишутся прямо по формуле обхода с учетом спецификации представления вершин дерева. Например, ниже приведена процедура смешанного обхода бинарного дерева дихотомии, реализующего формулу ЛКП.

   TYPE Вершина = POINTER TO Элемент ;

        Элемент = RECORD

                   Info : CARDINAL ;

                   LLink,RLink : Вершина

                  END ;

  PROCEDURE  Смеш_Обход (K : Вершина);

    BEGIN         

     IF K # NIL THEN              

         Смеш_Обход (K^.LLink); (* Обход левого поддерева *)

         WriteCard (K^.Info);  (* Обработка корня *)

         Смеш_Обход (K^.RLink); (* Обход правого  поддерева *)                             

     END

   END Смеш_Обход.

В традиционном программировании рекурсия часто рассматривается как некоторый заменитель итерации. Причем в качестве примеров рассматривается вычисление рекуррентных последовательностей, которые могут быть легко сформированы и обычными итераторами (циклами WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не имеет альтернатив в виде итераторов только тогда, когда  решение задач проводится на рекурсивных структурах. Попробуйте написать процедуру Смеш-Обход без использования рекурсии, только на основе циклов и, если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной процедуры по наглядности, лаконичности, выразительности.

Преимущества  и недостатки рекурсивного алгоритма

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

Преимущества рекурсии заключается в следующих аспектах:

• Часто это наиболее легкий метод написания алгоритма для задач, которые можно решить с помощью рекурсии (число Фибоначчи, факториал);
• Рекурсивно реализованные алгоритмы, при правильных на то основаниях, имеют лаконичную запись и менее трудоёмки при последующей отладке и модификации, они сокращают временные затраты на разработку, отладку и модификацию программных средств;
• Целый ряд структур данных и многие объекты современных языков программирования рекурсивны по самой своей сути (фрактальные объекты, иерархия классов в объектно-ориентированном программировании, древовидные регулярные структуры данных) и программы для работы с такими структурами выглядят намного более естественно в рекурсивной реализации;
• Рекурсия делает код более читабельным (позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной), что облегчает отладку;
• Рекурсия защищает от ошибок типа: «действия выполнены в неверном порядке», «использована неинициализированная переменная» и других аналогичных.

Недостатки рекурсии заключаются в следующем:

• Велика возможность войти в бесконечный цикл;
• При использовании некоторых формул слишком большие затраты памяти компьютера (к примеру, при вычислении числа Фибоначчи или факториалов, необходимо запоминать все значения чисел и вычислять одни и те же значения по многу раз);
• В случае если вызываемых функций будет очень много, может произойти переполнение стека;
• Следует избегать использования рекурсии в случаях, когда требуется высокая эффективность, так как они требуют времени и дополнительных затрат памяти и обладают худшей временной эффективностью.

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

Примеры решения  задач с помощью рекурсии

«Ханойская башня»

Задача: Имеется три стержня, на один из которых нанизаны N колец, причем кольца отличаются размером и лежат меньшее на большем. Требуется перенести пирамиду из N колец с одного стержня на другой за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Решение: На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

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

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

Рис. 7 Схема « Три стержня A, B и C»

Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись  переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы наступит конец света. Монахи все еще работают и, надеемся, еще долго будут работать.

Нетрудно решить эту задачу для двух дисков. Обозначая  перемещения диска, например, с площадки А на В так: А→В. Напишем алгоритм для этого случая: А→С; А→В; С→В. Всего 3 хода.

Для трех дисков алгоритм длиннее: А→В; А→С; В→С; А→В; С→А; С→В; А→В. В этом случае уже требуется 7 ходов.

Подсчитать  количество ходов (N) для k дисков можно по следующей рекуррентной формуле:  N(k)=2xN(k-1)+1.

Например, N(10)=1023, N(20)=104857. А вот сколько перемещений нужно сделать ханойским монахам: N(64)=18446744073709551615.

Теперь составим программу, по которой машина рассчитает алгоритм работы монахов и выведет  для любого значения N (количество дисков). Пусть на площадке А находятся N дисков.

Алгоритм решения  задачи будет следующим:

                1)Если N=0, то ничего не делать.

                2)Если N>0, то переместить (N-1) диск на С через В;

                          ● Переместить диск с А на В (А→В);

                          ● Переместить (N-1) диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь  три состояния.

Рис. 8 Схема «Перемещие дисков со стержня A на стержень B»

Описание алгоритма  имеет явно рекурсивный характер.

А теперь построим программу на Паскале. В ней имеется  рекурсивная процедура Hanoy, выполнение которой заканчивается только при N=0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде: 1→2; 1→3; 2→3 и т.д.

Программа на языке  Паскаль:

program monahi;

var n: byte;

procedure hanoy (n: byte; a,b,c:char);

begin

     if n>0 then

     begin hanoi (n-1,a,c,b);

     writeln(a,'=>',b);

    hanoi(n-1,c,b,a)

     end

end;

begin

     writeln('“Укажите число дисков:');

     readln(n);

     hanoi(n,'1','2','3')

end.

Вычисление  факториала

Факториал числа  представляет собой произведение всех натуральных чисел от 1 до этого  числа включительно. Например, факториал числа 7 выглядит так: 1*2*3*4*5*6*7.

Факториал числа  обозначается как само число, после  которого следует восклицательный  знак. Например, 7!.  Таким образом: 7!=1*2*3*4*56*7=5040.

С увеличением  числа его факториал быстро возрастает. Так если 3!=6, то уже 10!=3628800. Поэтому для натуральных чисел больше 12-ти в языке программирования Паскаль просто так факториал вычислить нельзя.

Алгоритм решения  задачи:

Переменной factorial сначала присваивается значение 1. 0!=1 и 1!=1.