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