Рекурсивные структуры в алгоритмах

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


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

выделить самоподобие задачи.

любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал:
У

попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:

У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…

непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например,

функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

визуальный образ происходящего представлен на рис. 2.

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

3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

а та в свою очередь вызывает A. Это называется сложной

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

Опережающее описание процедуры B позволяет вызывать ее из процедуры A.

сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки

с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию.

из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

служит раздел дискретной математики, изучающий деревья.


Определение: Деревом будем называть конечное

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

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

тоже являются деревьями.

Рисунок 5 - Дерево.

представлены ниже.
Рисунок 6 - Другие способы изображения древовидных структур: (а)

вложенные множества; (б) вложенные скобки; (в) уступчатый список.

и та же идея, а именно идея прохождения или обхода

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

Алгоритм обхода в прямом порядке:
Попасть в корень,
Пройти все поддеревья слева на право в прямом порядке.

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

В частности для дерева на рисунках 5 и 6 прямой обход дает последовательность узлов: A, B, C, D, E, G, H.

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

крайнее правое поддерево.

То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рисунках 5 и 6 это дает последовательность узлов: B, A, D, C, E, G, F.

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

7 - Деревце

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

отмечающим середину мира, находится бронзовый диск, на котором укреплены 3

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

французский математик Эдуард Люка

Рисунок 8 - Головоломка «Ханойские башни».

n дисков надо действовать следующим образом:
    1) Перекладываем n-1 диск.     2) Перекладываем

n-й диск на оставшийся свободным штырь.     3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.
Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество дисков.

из частей, подобных всей фигуре.

Классическим примером является кривая Коха, построение

которой показано на рисунке 9. Изначально берется отрезок прямой (рисунке 9а).

Рисунок 9 - Процесс построения кривой Коха

нее строится угол (рисунке 9б), стороны которого равны длине изъятого

отрезка (то есть 1/3 от длины исходного отрезка ).

Рисунок 9 - Процесс построения кривой Коха

9в).
Рисунок 9 - Процесс построения кривой Коха
Рисунок 9 -

Процесс построения кривой Коха

И так далее (рисунке 9г).

построение можно прекратить, когда размер деталей окажется меньше разрешения экрана

(рисунке 9д).

Рисунок 9 - Процесс построения кривой Коха

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

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

Так почему же люди продолжают пользоваться рекурсивными алгоритмами? Очевидно, потому что это проще и естественнее, чем соответствующие нерекурсивные решения.

определение теоретически способно описывать бесконечно большое число объектов. С помощью

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

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

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