Итерация — это повторение процесса с целью создания (возможно, неограниченной) последовательности результатов. Каждое повторение процесса представляет собой одну итерацию, а результат каждой итерации является отправной точкой следующей итерации.
В математике и информатике итерация (наряду со связанным с ней методом рекурсии ) является стандартным элементом алгоритмов .
В математике итерация может относиться к процессу итерации функции , т.е. многократному применению функции с использованием результатов одной итерации в качестве входных данных для следующей. Итерация, казалось бы, простых функций может привести к сложному поведению и трудным проблемам — например, см. гипотезу Коллатца и последовательности жонглеров .
Другое применение итерации в математике — это итерационные методы , которые используются для получения приближенных численных решений определенных математических задач. Метод Ньютона является примером итерационного метода. Ручное вычисление квадратного корня числа является распространенным явлением и хорошо известным примером.
В вычислительной технике итерация — это метод выделения блока операторов в компьютерной программе для определенного количества повторений. Говорят, что этот блок операторов повторяется ; ученый-компьютерщик может также назвать этот блок операторов « итерацией ».
Циклы представляют собой наиболее распространенные языковые конструкции для выполнения итераций. Следующий псевдокод трижды «итерирует» строку кода между началом и концом цикла for и использует значения i в качестве приращений.
a := 0 for i := от 1 до 3 do {цикл три раза } Begin a := a + i ; {добавляем текущее значение i в конец } ; распечатать ( а ) ; { выведено число 6 (0 + 1; 1 + 2; 3 + 3) } Допустимо и часто необходимо использовать значения из других частей программы за пределами блока операторов, заключенного в скобки, для выполнения желаемой функции.
Итераторы представляют собой альтернативные циклам языковые конструкции, которые обеспечивают согласованные итерации над конкретными структурами данных. В конечном итоге они могут сэкономить время и усилия при последующих попытках кодирования. В частности, итератор позволяет повторять одну и ту же операцию на каждом узле такой структуры данных, часто в некотором заранее определенном порядке.
Итераторы — это чисто функциональные языковые конструкции, которые принимают или отклоняют данные во время итераций.
Рекурсии и итерации имеют разные алгоритмические определения, хотя они могут генерировать одинаковые эффекты/результаты. Основное отличие состоит в том, что рекурсию можно использовать в качестве решения без предварительного знания того, сколько раз действие придется повторить, тогда как успешная итерация требует такого предварительного знания.
Некоторые типы языков программирования, известные как функциональные языки программирования , спроектированы таким образом, что в них не создается блок операторов для явного повторения, как в случае цикла for . Вместо этого эти языки программирования используют исключительно рекурсию . Вместо того, чтобы вызывать блок кода, который должен быть повторен заранее определенное количество раз, исполняемый блок кода вместо этого «делит» работу, которую необходимо выполнить, на несколько отдельных частей, после чего блок кода выполняется на каждой отдельной части. . Каждая часть работы будет многократно делиться до тех пор, пока «объем» работы не станет настолько маленьким, насколько это возможно, и в этот момент алгоритм выполнит эту работу очень быстро. Затем алгоритм «переворачивает» и собирает части в единое целое.
Классический пример рекурсии — алгоритмы сортировки списков, такие как сортировка слиянием . Рекурсивный алгоритм сортировки слиянием сначала многократно разделит список на последовательные пары; Затем упорядочивается каждая пара, затем каждая последовательная пара пар и т. д., пока элементы списка не окажутся в желаемом порядке.
Код ниже представляет собой пример рекурсивного алгоритма на языке программирования Scheme , который выводит тот же результат, что и псевдокод под предыдущим заголовком.
( пусть итерирует (( i 1 ) ( a 0 )) ( if ( <= i 3 ) ( итерирует ( + i 1 ) ( + a i )) ( отображает a ))) В некоторых педагогических школах итерации используются для описания процесса обучения или направления учащихся к повторению экспериментов, оценок или проектов до тех пор, пока не будут найдены более точные результаты или пока учащийся не овладеет техническими навыками. Эта идея содержится в старой поговорке: «Практика ведет к совершенству». В частности, «итеративный» определяется как «процесс обучения и развития, включающий циклические исследования, дающий людям множество возможностей пересмотреть идеи и критически осмыслить их последствия». [1]
В отличие от информатики и математики, образовательные итерации не предопределены; вместо этого задача повторяется до тех пор, пока не будет достигнут успех по некоторым внешним критериям (часто тесту).