Итерация - Iteration

Итерация - это повторение процесса с целью создания (возможно, неограниченной) последовательности результатов. Каждое повторение процесса является одной итерацией, и результат каждой итерации является отправной точкой следующей итерации.

В математике и информатике итерация (вместе с соответствующей техникой рекурсии ) является стандартным элементом алгоритмов .

По математике

В математике итерация может относиться к процессу итерации функции , то есть многократного применения функции с использованием выходных данных одной итерации в качестве входных данных для следующей. Итерация, казалось бы, простых функций может привести к сложному поведению и трудным проблемам - например, см. Гипотезу Коллатца и последовательности жонглера .

Другое использование итераций в математике - это итерационные методы, которые используются для получения приближенных численных решений определенных математических задач. Метод Ньютона - пример итеративного метода. Вычисление квадратного корня числа вручную - распространенное использование и хорошо известный пример.

В вычислениях

В вычислениях итерация - это метод выделения блока операторов в компьютерной программе на определенное количество повторений. Говорят, что этот блок операторов повторяется ; компьютерный ученый может также относиться к этому блоку операторов в качестве «итерации».

Псевдокод ниже приведен пример итерации; строка кода между скобками цикла for будет "повторяться" три раза:

a = 0
for i from 1 to 3        // loop three times
{
    a = a + i            // add the current value of i to a
}
print a                  // the number 6 is printed (0 + 1; 1 + 2; 3 + 3)

Допустимо и часто необходимо использовать значения из других частей программы за пределами заключенного в квадратные скобки блока операторов для выполнения желаемой функции. В приведенном выше примере строка кода использует значение i по мере увеличения.

Связь с рекурсией

В алгоритмических ситуациях рекурсия и итерация могут использоваться с тем же эффектом. Основное отличие состоит в том, что рекурсию можно использовать в качестве решения, не зная заранее, сколько раз действие придется повторять, в то время как для успешной итерации требуется это предвидение.

Некоторые типы языков программирования, известные как языки функционального программирования , спроектированы таким образом, что они не устанавливают блок операторов для явного повторения, как в случае цикла for . Вместо этого в этих языках программирования используется исключительно рекурсия . Вместо того, чтобы вызывать блок кода, который должен быть повторен заранее определенное количество раз, исполняемый блок кода вместо этого «разделяет» работу, которая должна быть выполнена, на несколько отдельных частей, после чего блок кода выполняется сам для каждой отдельной части. Каждая часть работы будет многократно разделена до тех пор, пока «объем» работы не станет настолько маленьким, насколько это возможно, после чего алгоритм выполнит эту работу очень быстро. Затем алгоритм «переворачивает» и собирает части в единое целое.

Классический пример рекурсии - это алгоритмы сортировки списков, такие как сортировка слиянием . Рекурсивный алгоритм сортировки слиянием сначала повторно разделит список на последовательные пары; затем упорядочивается каждая пара, затем каждая последующая пара пар и так далее, пока элементы списка не будут расположены в желаемом порядке.

Приведенный ниже код является примером рекурсивного алгоритма на языке программирования Scheme, который выдаст тот же результат, что и псевдокод под предыдущим заголовком.

(let iterate ((i 1) (a 0))
  (if (<= i 3)
    (iterate (+ i 1) (+ a i))
    (display a)))

Другая терминология

В объектно-ориентированном программировании , итератор является объектом , который обеспечивает итерацию выполняется таким же образом , для ряда различных структур данных, что экономит время и усилие , в более поздних попытках кодирования. В частности, итератор позволяет повторять операции одного и того же типа на каждом узле такой структуры данных, часто в некотором заранее определенном порядке.

Iteratee есть абстракция , которая принимает или отклоняет данные в процессе итерации.

Образование

В некоторых педагогических школах итерации используются для описания процесса обучения или побуждения учащихся к повторению экспериментов, оценок или проектов до тех пор, пока не будут получены более точные результаты или пока учащийся не овладеет техническими навыками. Эта идея содержится в старой пословице: «Практика приводит к совершенству». В частности, «итеративный» определяется как «процесс обучения и развития, который включает в себя циклическое исследование, дающее людям множество возможностей пересмотреть идеи и критически осмыслить их значение».

В отличие от вычислений и математики, образовательные итерации не предопределены; вместо этого задача повторяется до тех пор, пока не будет достигнут успех по некоторым внешним критериям (часто тестированию).

Смотрите также

использованная литература