Итерация и рекурсия в программировании.
Итерация в программировании
Итерация - это организации обработки данных, при котором действия повторяются многократно, не приводя при этом к вызовам самих себя.
Когда какое-то действие необходимо повторить большое количество раз, в программировании используются циклы. Например, нужно вывести 100 раз на экран текст «Hello, World!». Вместо 100-кратного повторения одной и той же команды вывода текста часто создается цикл, который прокручивается 100 раз, и 100 раз выполняет то, что написано в теле цикла. Один шаг цикла и называется итерацией.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций.
Следует избегать избыточной глубины рекурсии, так как это может вызвать переполнение стека вызовов.
Итеративная и рекурсивная схема организации
вычислительного процесса
Для того чтобы лучше понять особенности рекурсивных алгоритмов, полезно сопоставить итеративнную и рекурсивную огранизацию процесса вычислений в программе. Особенности итеративного и рекурсивного вычислительного процесса рассмотрим на примере вычисления значения факториала некоторого натурального числа N.
Итеративная схема организации вычислительного процесса
Итеративный процесс можно проиллюстрировать с помощью схемы, приведенной на рис. 55. Этот процесс состоит из четырех блоков: инициализации, принятия решения (о продолжении вычислений), вычисления и модификации.
В основе итеративного вычислительного процесса лежит итеративный цикл While, Repeat-Until, For. Наиболее общим является цикл While:
While < условие цикла > do < тело цикла >;
Итеративная схема вычисления факториала:
N! = 1 * 2 * 3 * … * N.
Процедура, реализующая итеративную схему вычисления факториала:
Procedure Iter_Fact ( n: word; var f: word );
Var i: word;
begin
i:=1; f:=1; { инициализация }
while i < = n do begin { решение о завершении }
f:= f * i; { вычисления }
inc( i ); { модификация }
end;
end;
Существует два важных положения, известных в математике и в программировании, определяющих соотношение между итерацией и рекурсией.
1. Любой итеративный цикл может быть заменен рекурсией.
2. Рекурсия не всегда может быть заменена итерацией.
Рекурсивная схема организации вычислительного процесса
Общая схема рекурсивного вычислительного процесса представлена на рис. 56
Так как обращаться к рекурсивной процедуре можно как из нее самой, так и извне, каждое обращение к рекурсивной процедуре вызывает ее независимую активацию. При каждой активации образуются копии всех локальных переменных и формальных параметров рекурсивной процедуры, в которых “оставляют следы” операторы текущей активации. Таким образом, для рекурсивной процедуры может одновременно существовать несколько активаций. Для обеспечения правильного функционирования рекурсивной процедуры необходимо сохранять адреса возврата в таком порядке, чтобы возврат после завершения каждой текущей активации выполнялся в точку, соответствующую оператору, непосредственно следующему за оператором рекурсивного вызова. Совокупность локальных переменных, формальных параметров рекурсивной процедуры и адреса возврата однозначно характеризует текущую активацию и образует фрейм активации. Фрейм активации необходимо сохранять при очередной активации и восстанавливать после завершения текущей активации.
В блоке принятия решения (о продолжении вычислений) производится проверка, являются ли значения входных параметров такими, для которых возможно вычисление значений выходных параметров в соответствии с базисной частью рекурсивного определения. На основании этой проверки принимается решение о выполнении промежуточных или окончательных вычислений. Блок промежуточных вычислений можно объединить с блоком обращения к процедуре, если промежуточные вычисления очень просты. В блоке окончательных вычислений производится явное определение параметров-переменных процедуры для конкретных значений входных параметров, соответствующих текущей активации процедуры.
В основе рекурсивного вычислительного процесса лежит рекурсивный цикл, который реализуется через вызов рекурсивной процедуры, причем каждая активация рекурсивной процедуры эквивалентна одному проходу итеративного цикла While.
Общая схема рекурсивного цикла:
Procedure Рекурсивный_Цикл (…);
begin
if < условие цикла > then
begin
< тело рекурсивного цикла; >
Рекурсивный_Цикл (…);
end;
end;
В теле рекурсивного цикла (в блоке промежуточных вычислений) обязательно должны содержаться операторы, изменяющие значения переменных, от которых зависит условие завершения рекурсивного цикла. Напомним, что выполнение условия завершения рекурсивного цикла соответствует достижению базиса рекурсивного определения. Если значения этих переменных не успевают измениться до очередной активации рекурсивной процедуры, возникает бесконечный рекурсивный цикл.
Общая схема бесконечного рекурсивного цикла:
Procedure Бесконечный_Рекурсивный_Цикл (…);
begin
if < условие цикла > then
begin
Бесконечный_Рекурсивный_Цикл (…);
< тело рекурсивного цикла; >
end;
end;