Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии
Лекция 14
Рекурсия и рекурсивные алгоритмы
В окружающем нас мире часто можно встретить объекты, обладающие самоподобием. То есть часть большого объекта в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления, схожие с самим деревом. Приведенные ниже графические объекты также обладают самоподобием. Такие объекты называются рекурсивными.
При первичном осмыслении понятие рекурсии достаточно просто и не требует специальных знаний. Иногда на рекурсию смотрят как на наличие в определении объекта ссылки на сам объект или проявление свойств самоповторения (при этом сколь угодно малая часть объекта подобна всему объекту в целом). Общий случай проявления рекурсивности может быть сформулирован как наличие циклических взаимных обращений в определении объекта, которые в итоге замыкаются на сам объект.
В технике процедурного программирования рекурсивность в построении подпрограмм проявляется в разработке управляющих структур, которые при выполнении обращаются сами к себе непосредственно или через цепочку других аналогичных структур. Бесконечность и незавершенность таких обращений кажущаяся, так как при достижении определенных условий самовызовы завершаются. Во многих конкретных случаях простыми рассуждениями путем отслеживания значений одной или нескольких управляющих величин удается провести доказательство завершимости рекурсивных вычислений за конечное число шагов.
|
|
|
Рекурсия рассматривается как альтернатива итерации.
Рекурсивность в постановке задачи проявляется, если решение для общего случая сводится к аналогичным задачам для меньшего количества входных данных. В таком контексте под рекурсией понимают прием последовательного сведения решения некоторой задачи к решению совокупности "более простых" задач такого же класса и получению на этой основе решения исходной задачи.
Рекурсия в широком смысле – это определение объекта посредством ссылки на себя.
Рекурсия - свойство алгоритмической системы на промежуточных этапах своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе. При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания.
Рекурсивный алгоритм – это алгоритм, в описании которого прямо или косвенно содержится обращение к самому себе.
Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров. Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n, то есть имеет место зависимость: Sn=Sn-1+n. Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу.
|
|
|
При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров. Такая организация обращений называется косвенной рекурсией. Образно косвенную рекурсию можно описать так. Перед зеркалом 1 стоит зеркало 2, в котором отражается само зеркало 1. В последнем видно зеркало. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: одно их них – это последний элемент массива, а другое является максимальным элементом в массиве размера (n-1). Для нахождения максимального элемента массива размера (n-1) применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива.
|
|
|
Рекурсивный метод в программировании предполагает разработку решения задачи, основываясь на свойствах рекурсивности отдельных объектов или закономерностей. При этом исходная задача сводится к решению аналогичных подзадач, которые являются более простыми и отличаются другим набором параметров.
Сущность рекурсии
Пример рекурсивной процедуры:
| 1 2 3 4 5 6 | procedure Rec(a: integer); begin if a>0 then Rec(a-1); writeln(a); end; |
Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3 
Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.
Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.
|
|
|
Разработке рекурсивных алгоритмов предшествует рекурсивная триада – этапы моделирования задачи, на которых определяется набор параметров и соотношений между ними. Рекурсивную триаду составляют параметризация, выделение базы и декомпозиция.
На этапе параметризации из постановки задачи выделяются параметры, которые описывают исходные данные. При этом некоторые дальнейшие разработки решения могут требовать введения дополнительных параметров, которые не оговорены в условии, но используются при составлении зависимостей. Необходимость в дополнительных параметрах часто возникает также при решении задач оптимизации рекурсивных алгоритмов, в ходе которых сокращается их временная сложность.
Выделение базы рекурсии предполагает нахождение в решаемой задаче тривиальных случаев, результат для которых очевиден и не требует проведения расчетов. Верно найденная база рекурсии обеспечивает завершенность рекурсивных обращений, которые в конечном итоге сводятся к базовому случаю. Переопределение базы или ее динамическое расширение в ходе решения задачи часто позволяют оптимизировать рекурсивный алгоритм за счет достижения базового случая за более короткий путь обращений.
Декомпозиция представляет собой сведение общего случая к более простым подзадачам, которые отличаются от исходной задачи набором входных данных. Декомпозиционные зависимости описывают не только связь между задачей и подзадачами, но и характер изменения значений параметров на очередном шаге. От выбранных отношений зависит трудоемкость алгоритма, так как для одной и той же задачи могут быть составлены различные зависимости. Пересмотр отношений декомпозиции целесообразно проводить комплексно, то есть параллельно с корректировкой параметров и анализом базовых случаев.
Рекурсия изнутри
program Rec_2_2;
var i: integer;
function Pow (x: real; n: integer):real;
begin
writeln('прямой ход',’ x=',x,' n=',n);
if n=0 then
begin
writeln('завершение рекурсивных вызовов');
Pow:=1
end
else
Pow:=x*Pow(x,n-1);
writeln('обратный ход',’ n=',n);
end;
begin
writeln('Pow(2,3)=',Pow(2,3))
end.
Результат работы программы:
прямой ход x=2 n=3
прямой ход x=2 n=2
прямой ход x=2 n=1
прямой ход x=2 n=0
завершение рекурсивных вызовов
обратный ход n=0
обратный ход n=1
обратный ход n=2
обратный ход n=3
Pow(2,3)=8
Область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении, образует рекурсивный стек.
Ø Для каждого текущего обращения формируется локальный слой данных стека (при этом совпадающие идентификаторы разных слоев стека независимы друг от друга и не отождествляются).
Ø Завершение вычислений происходит посредством восстановления значений данных каждого слоя в порядке, обратном рекурсивным обращениям.
К оличество рекурсивных обращений ограничено размером области памяти, выделяемой под программный код. При заполнении всей предоставленной области памяти попытка вызова следующего рекурсивного обращения приводит к ошибке переполнения стека.
Задача о разрезании прямоугольника на квадраты.
Дан прямоугольник, стороны которого выражены натуральными числами. Разрежьте его на минимальное число квадратов с натуральными сторонами. Найдите число получившихся квадратов.
Разработаем рекурсивную триаду.
Параметризация: m, n–натуральные числа, соответствующие размерам прямоугольника.
База рекурсии: для m=n число получившихся квадратов равно 1, так как данный прямоугольник уже является квадратом.
Декомпозиция: если 
, то возможны два случая m < n или m > n. Отрежем от прямоугольника наибольший по площади квадрат с натуральными сторонами. Длина стороны такого квадрата равна наименьшей из сторон прямоугольника. После того, как квадрат будет отрезан, размеры прямоугольника станут следующие: большая сторона уменьшится на длину стороны квадрата, а меньшая не изменится. Число искомых квадратов будет вычисляться как число квадратов, на которые будет разрезан полученный прямоугольник, плюс один (отрезанный квадрат). К получившемуся прямоугольнику применим аналогичные рассуждения: проверим на соответствие базе или перейдем к декомпозиции.
Var a,b,k:byte;
Function kv(m,n:byte):byte;
begin
if m=n then kv:=1 else //база рекурсии
if m>n then kv:=1+kv(m-n,n) //декомпозиция для m>n
else kv:= 1+kv(m,n-m); //декомпозиция для m<n
end;
begin
writeln(‘Введите стороны прямоугольника’);
readln(a,b);
k = kv(a,b);
writeln(‘Прямоугольник со сторонами ’,a,’ и ‘,b,’ можно разрезать на ‘,k,’ квадратов’);
end.
Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии
Рекурсивные алгоритмы относятся к классу алгоритмов с высокой ресурсоемкостью, так как при большом количестве самовызовов рекурсивных функций происходит быстрое заполнение стековой области. Кроме того, организация хранения и закрытия очередного слоя рекурсивного стека являются дополнительными операциями, требующими временных затрат. На трудоемкость рекурсивных алгоритмов влияет и количество передаваемых функцией параметров.
Рассмотрим один из методов анализа трудоемкости рекурсивного алгоритма, который строится на основе подсчета вершин рекурсивного дерева. Для оценки трудоемкости рекурсивных алгоритмов строится полное дерево рекурсии. Оно представляет собой граф, вершинами которого являются наборы фактических параметров при всех вызовах функции, начиная с первого обращения к ней, а ребрами – пары таких наборов, соответствующих взаимным вызовам. При этом вершины дерева рекурсии соответствуют фактическим вызовам рекурсивных функций. Следует заметить, что одни и те же наборы параметров могут соответствовать разным вершинам дерева. Корень полного дерева рекурсивных вызовов – это вершина полного дерева рекурсии, соответствующая начальному обращению к функции.
Важной характеристикой рекурсивного алгоритма является глубина рекурсивных вызовов– наибольшее одновременное количество рекурсивных обращений функции, определяющее максимальное количество слоев рекурсивного стека, в котором осуществляется хранение отложенных вычислений. Количество элементов полных рекурсивных обращений всегда не меньше глубины рекурсивных вызовов. При разработке рекурсивных программ необходимо учитывать, что глубина рекурсивных вызовов не должна превосходить максимального размера стека используемой вычислительной среды.
При этом объем рекурсии - это одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы.
Будем использовать следующие обозначения для конкретного входного параметра D:
R(D)– общее число вершин дерева рекурсии,
RV(D)– объем рекурсии без листьев (внутренние вершины),
RL(D)– количество листьев дерева рекурсии,
HR(D)– глубина рекурсии.
| R(D)=6 |
| RV(D)=4 |
| RL(D)=1 |
| HR(D)=6 |
Дата добавления: 2022-01-22; просмотров: 27; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!