Исследование понятия рекурсии в программировании. Описание метода, который позволяет разбить задачу на части все меньшего и меньшего размера. Изучение схемы работы рекурсивной процедуры. Способы изображения древовидных структур. Избавление от рекурсии.
Аннотация к работе
Рекурсия используется, когда можно выделить самоподобие задачи.В искусстве рекурсия выглядит примерно так :Или как в народной песенке: У попа была собака, он ее любил, Она съела кусок мяса, он ее убил, В землю закопал, Надпись написал: У попа была собака, он ее любил, Она съела кусок мяса, он ее убил, В землю закопал, Надпись написал: У попа была собака, он ее любил, Она съела кусок мяса, он ее убил, В землю закопал, Надпись написал: …В программировании рекурсия - вызов функции (процедуры) из нее же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция Количество вложенных вызовов функции или процедуры называется глубиной рекурсии .Рисунок 1 - Блок схема работы рекурсивной процедуры Для функции Rec , где входной параметр целое число, функция проверяет, является ли число положительным, запускает сама себя с параметром меньшим, чем входной на единицу, затем печатает входной параметр. 2.Рисунок 2 - Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. Рисунок из алхимического трактата «Synosius » Теодора Пелеканоса (1478г).Рисунок 4 - Сложная рекурсия.Теоретической базой для рекурсивных функций, вызывающих себя более одного раза, служит раздел дискретной математики, изучающий деревья. Определение: Деревом будем называть конечное множество T , состоящее из одного или более узлов, таких что: а) Имеется один специальный узел, называемый корнем данного дерева. б) Остальные узлы (исключая корень) содержатся в попарно непересекающихся подмножествах , каждое из которых в свою очередь является деревом.