На этом шаге мы рассмотрим итерацию.
Рекурсия и итерация в некотором смысле противоположны. Рекурсия решает задачу от сложного к простому, итерация - от простого к сложному. Текст рекурсивного алгоритма выражает сложный объект через более простой (более простые) такого же типа. Текст итеративного алгоритма описывает процесс строительства, начиная с мелких деталей.
Рекурсивный алгоритм выражает неизвестное через неизвестное, но связь между этими двумя неизвестными довольно проста, математически прозрачна, поэтому доказать правильность алгоритма легко.
Состояния объекта на двух разных шагах итеративного алгоритма - как два состояния недостроенного дома: пока не положен последний кирпич, не очевидно, что получится в конце. Поэтому доказать правильность такого алгоритма обычно довольно сложно.
Ранее нами рассматривались рекурсивные алгоритмы. Но во многих случаях та же задача может быть решена и нерекурсивными методами. Рекурсивный подход к вычислению функций, заданных рекуррентными соотношениями:
f(n) = φ(f(n-1), n); f(0) = а.
Эту последовательность можно обратить:
f(0) = а; f(1) = φ(f(0),1); f(2) = φ(f(1),2); ... f(1) = φ(f(n-1),n),
начав вычисление с отыскания значения функции при минимальном значении аргумента, и используя его для определения следующего и так далее. Такое вычисление, записанное в виде:
y := a; for i:= 1 to n do у := φ(y, i)
называется итерацией.
Важное различие между рекурсией и итерацией состоит в механизме реализации. Исполнитель рекурсивного алгоритма, как видно ранее, сводит неизвестное к другому неизвестному, накапливая информацию и откладывая реальные вычисления до момента сведения аргумента функции к такому значению, при котором значение функции известно. Исполнитель итеративного алгоритма начинает с известного значения и шаг за шагом преобразует известные уже значения функции в значения для больших аргументов. В этом отношении итерация подобна обратному ходу в реализации рекурсии. Из этих слов (итерационный процесс есть часть рекурсивного) можно сделать вывод о том, что итерация проще (как часть целого) и необходимо решать задачи итерационными методами.
В действительности ситуация сложнее. В нескольких словах ее можно охарактеризовать так: рекурсивное решение задачи состоит из двух частей - прямого хода (сведение задачи к итерационной форме) и обратного (выполнение итераций). Освободив машину от выполнения прямого хода, облегчаем ее работу, но перекладываем эту часть работы на программиста, которому вменяется в обязанность преобразовать программу. Иногда это не составляет труда для программиста, и он сразу может написать итерационный вариант (например, вычисления факториала или чисел Фибоначчи), а иногда проблема будет трудно разрешимой.
На следующем шаге мы рассмотрим связь между рекурсией итерацией.
