Рекурсия изнутри
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 |
