Описание рекурсивного алгоритма
Описание рекурсивного алгоритмаСкачать файл - Описание рекурсивного алгоритма
Одной из идей процедурного программирования , которая оформилась в начале шестидесятых годов ХХ века, стало активное применение в практике программирования некоторого метода, основанного на организации серий взаимных обращений программ функций друг к другу. Вопросы об эффективности использования данного метода при разработке алгоритмических моделей актуальны и в настоящее время, несмотря на существование различных парадигм программирования , создание новых и совершенствование существующих языков программирования. Речь идет о рекурсивном методе в программировании, который рассматривается альтернативным по отношению к итерационному. Рекурсия — это определение объекта через обращение к самому себе. Рекурсивный алгоритм — это алгоритм , в описании которого прямо или косвенно содержится обращение к самому себе. В технике процедурного программирования данное понятие распространяется на функцию, которая реализует решение отдельного блока задачи посредством вызова из своего тела других функций, в том числе и себя самой. Если при этом на очередном этапе работы функция организует обращение к самой себе, то такая функция является рекурсивной. Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых n-1 чисел сложить с числом n , то есть имеет место зависимость: Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу. При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров. Такая организация обращений называется косвенной рекурсией. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: Для нахождения максимального элемента массива размера n-1 применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива. Рекурсивный метод в программировании предполагает разработку решения задачи, основываясь на свойствах рекурсивности отдельных объектов или закономерностей. При этом исходная задача сводится к решению аналогичных подзадач, которые являются более простыми и отличаются другим набором параметров. Разработке рекурсивных алгоритмов предшествует рекурсивная триада — этапы моделирования задачи, на которых определяется набор параметров и соотношений между ними. Рекурсивную триаду составляют параметризация , выделение базы и декомпозиция. На этапе параметризации из постановки задачи выделяются параметры, которые описывают исходные данные. При этом некоторые дальнейшие разработки решения могут требовать введения дополнительных параметров, которые не оговорены в условии, но используются при составлении зависимостей. Необходимость в дополнительных параметрах часто возникает также при решении задач оптимизации рекурсивных алгоритмов, в ходе которых сокращается их временная сложность. Выделение базы рекурсии предполагает нахождение в решаемой задаче тривиальных случаев, результат для которых очевиден и не требует проведения расчетов. Верно найденная база рекурсии обеспечивает завершенность рекурсивных обращений, которые в конечном итоге сводятся к базовому случаю. Переопределение базы или ее динамическое расширение в ходе решения задачи часто позволяют оптимизировать рекурсивный алгоритм за счет достижения базового случая за более короткий путь обращений. Декомпозиция представляет собой сведение общего случая к более простым подзадачам, которые отличаются от исходной задачи набором входных данных. Декомпозиционные зависимости описывают не только связь между задачей и подзадачами, но и характер изменения значений параметров на очередном шаге. От выбранных отношений зависит трудоемкость алгоритма, так как для одной и той же задачи могут быть составлены различные зависимости. Пересмотр отношений декомпозиции целесообразно проводить комплексно, то есть параллельно с корректировкой параметров и анализом базовых случаев. Рекурсивные алгоритмы относятся к классу алгоритмов с высокой ресурсоемкостью, так как при большом количестве самовызовов рекурсивных функций происходит быстрое заполнение стековой области. Кроме того, организация хранения и закрытия очередного слоя рекурсивного стека являются дополнительными операциями, требующими временных затрат. На трудоемкость рекурсивных алгоритмов влияет и количество передаваемых функцией параметров. Рассмотрим один из методов анализа трудоемкости рекурсивного алгоритма, который строится на основе подсчета вершин рекурсивного дерева. Для оценки трудоемкости рекурсивных алгоритмов строится полное дерево рекурсии. Оно представляет собой граф , вершинами которого являются наборы фактических параметров при всех вызовах функции, начиная с первого обращения к ней, а ребрами — пары таких наборов, соответствующих взаимным вызовам. При этом вершины дерева рекурсии соответствуют фактическим вызовам рекурсивных функций. Следует заметить, что одни и те же наборы параметров могут соответствовать разным вершинам дерева. Корень полного дерева рекурсивных вызовов — это вершина полного дерева рекурсии, соответствующая начальному обращению к функции. Важной характеристикой рекурсивного алгоритма является глубина рекурсивных вызовов — наибольшее одновременное количество рекурсивных обращений функции, определяющее максимальное количество слоев рекурсивного стека, в котором осуществляется хранение отложенных вычислений. Количество элементов полных рекурсивных обращений всегда не меньше глубины рекурсивных вызовов. При разработке рекурсивных программ необходимо учитывать, что глубина рекурсивных вызовов не должна превосходить максимального размера стека используемой вычислительной среды. При этом объем рекурсии - это одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы. Будем использовать следующие обозначения для конкретного входного параметра D:. R D — общее число вершин дерева рекурсии,. R V D — объем рекурсии без листьев внутренние вершины ,. R L D — количество листьев дерева рекурсии,. H R D — глубина рекурсии. Например, для вычисления n -го члена последовательности Фибоначчи разработана следующая рекурсивная функция:. Тогда полное дерево рекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид рис. Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины. Задача о разрезании прямоугольника на квадраты. Дан прямоугольник , стороны которого выражены натуральными числами. Разрежьте его на минимальное число квадратов с натуральными сторонами. Найдите число получившихся квадратов. Отрежем от прямоугольника наибольший по площади квадрат с натуральными сторонами. Длина стороны такого квадрата равна наименьшей из сторон прямоугольника. После того, как квадрат будет отрезан, размеры прямоугольника станут следующие: Число искомых квадратов будет вычисляться как число квадратов, на которые будет разрезан полученный прямоугольник , плюс один отрезанный квадрат. К получившемуся прямоугольнику применим аналогичные рассуждения: Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины рис. Подскажите, пожалуйста, планируете ли вы возобновление программ высшего образования? Если да, есть ли какие-то примерные сроки? Мы ищем курсы, покупаем и публикуем их для вас бесплатно. Учеба Академии Учителя Рейтинг Вопросы Магазин. Курсы Школа Высшее образование Мини-МБА Профессиональная переподготовка Повышение квалификации Сертификации. Информация Глоссарий Дипломы Вопросы и ответы Студенты Рейтинг выпускников Мнения Учебные программы. Структуры и алгоритмы компьютерной обработки данных. Рекурсия и рекурсивные алгоритмы. В лекции рассматриваются основные понятия рекурсии в контексте разработки алгоритмов с помощью рекурсивной триады, дается представление о ресурсной эффективности и о методе оценки рекурсивных алгоритмов через подсчет вершин рекурсивного дерева. Пользовательское соглашение Политика конфиденциальности Реклама на сайте Напишите нам.
Рекурсия и рекурсивные алгоритмы
Характеристики самосвал камаз 453950с прицепом
Простейшие рекурсивные алгоритмы
Шаблон резюмена работу образец 2017
Подрулевой переключатель ауди 80 схема
Сталкер золотой обоз 2 где найти колбы
Лекция 9. Рекурсия Введение
Html таблица вертикальное выравнивание