Сравнение рекурсии и итерации
Итерация и рекурсия основаны на управляющих структурах: итерация использует структуру повторения, рекурсия использует структуру ветвления.
И итерация, и рекурсия подразумевают повторение: итерация использует структуру повторения явным образом, рекурсия – посредством повторных вызовов подпрограммы.
Итерация и рекурсия включают проверку на завершение: итерация завершается, когда перестаёт выполняться условие продолжения цикла, рекурсия завершается, когда распознаётся нерекурсивный случай.
Как итерация, так и рекурсия приближаются к завершению постепенно. Итерация с её проверкой повторения продолжает выполнять тело цикла, пока условие продолжения цикла не будет нарушено. Рекурсия продолжает производить более простые варианты первоначальной задачи, пока не будет достигнут нерекурсивный случай.
И итерация, и рекурсия может происходить бесконечно: итерация попадает в бесконечный цикл, если условие продолжения цикла никогда не становится ложным; рекурсия продолжается бесконечно, если шаг рекурсии не редуцирует задачу таким образом, что задача сходится к нерекурсивному случаю.
Рекурсия имеет отрицательные стороны. Она многократно инициализирует механизм вызова подпрограммы и увеличивает связанные с ним расходы процессорного времени и памяти (каждое рекурсивное обращение создаёт копию её параметров и локальных объектов). Итерация обычно происходит в пределах подпрограммы, так что здесь нет расходов на повторные вызовы подпрограммы и дополнительное выделение памяти. Отладка рекурсивной подпрограммы вызывает большие трудности, чем отладка итерационной подпрограммы.
|
|
|
Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами. Чтобы получить что-то, не имеющее простого нерекурсивного аналога, следует обратиться к процедурам и функциям, вызывающим себя два и более раз. В этом случае множество вызываемых процедур образует уже не цепочку, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения. (Алгоритмы обхода дерева, синтаксический анализ арифметических выражений, некоторые алгоритмы сортировки, задачи на графах, фракталы и т.д.)
Рекурсивная программа построения снежинки
Написать программу, строящую на экране изображение:
Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.
|
|
|
Пример рекурсивной программы построения окружностей
program recurs;
uses graph;
var x,y,r,d,m:integer;
procedure ris(x,y,r:integer);
var i:integer;
begin
if r<10 then exit;
circle(x,y,r);
for i:=1 to 1000 do; { просто цикл задержки }
ris(x+r,y,r*3 div 5);
ris(x-r,y,r*3 div 5);
end ;
begin {начало основной программы}
d:=detect;
initgraph(d,m,'e:\bp\bgi');
x:=320;
y:=240;
r:=120;
ris(x,y,r);
readln ;
end.
Ханойские башни
Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
|
|
|
В процессе требуется, чтобы больший диск ни разу не оказывался над меньшим. Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности.
Предположим, что существует решение для n-1 диска. Тогда для перекладывания n дисков надо действовать следующим образом:
1) Перекладываем n-1 диск.
2) Перекладываем n-й диск на оставшийся свободным штырь.
3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.
Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество дисков.
Создадим рекурсивную процедуру, печатающую всю последовательность перекладываний для заданного количества дисков. Такая процедура при каждом своем вызове должна печатать информацию об одном перекладывании (из пункта 2 алгоритма). Для перекладываний из пунктов (1) и (3) процедура вызовет сама себя с уменьшенным на единицу количеством дисков.
Дата добавления: 2022-01-22; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!