Итерация

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

Циклы бывают разными. Некоторые выполняются, пока верно или неверно определенное условие. Другие отрабатывают заданное количество раз. Соответственно, и итераций может быть разное количество. Встречаются циклы с бесконечным количеством итераций или такие, которые не выполнятся ни разу – там итераций будет ноль.

Например, цикл должен умножать число a на 10, пока оно не станет больше или равно 100. Если начальное значение a будет равно 10 – значит, цикл выполнится один раз: 10 * 10 = 100. Получится одна итерация. А вот если a = 0,1, то цикл выполнится уже трижды: 0,1 * 10 * 10 * 10 = 100. Выйдет три итерации.

Если же a изначально будет равно, скажем, 101, цикл не выполнится ни разу – ноль итераций.

Для чего нужны итерации

В разработке часто встречаются задачи, когда одно и то же действие нужно повторить несколько раз: вывести сообщение, получить или записать данные, отправить запрос и так далее. Делать это вручную неудобно и нарушает важный принцип программирования – DRY, don’t repeat yourself, или «не повторяйся». Вместо разработчика действие повторяет цикл – совершает нужное количество итераций.

В более узком смысле итерации помогают контролировать выполнение программы.

• Например, если сказать циклу «выполнись 10 раз», то он выполнится ровно столько раз – в этом можно быть уверенным.
• И наоборот: если мы сами не знаем, сколько итераций нужно, цикл будет проверять условие для завершения на каждой из них. Когда заданное разработчиком условие выполнится – он закончится. Так что считать итерации вручную не понадобится.

Поэтому итерации и циклы в целом – одно из базовых понятий в программировании. Они есть практически во всех популярных языках: Java, JavaScript, PHP, Python, C++ и так далее.

Как устроены итерации

Структура цикла. Когда программист объявляет цикл, он сначала описывает его условия – инструкции для выполнения. Например, он пишет условие для выхода из цикла или количество повторений.

После объявления пишется тело цикла. Это подпрограмма, которая обычно отделена от основного кода фигурными скобками или ключевыми словами begin и end. В Python для этого используются отступы.

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

В ходе каждой итерации тело цикла выполняется один раз. Потом программа снова проверяет условие – и так далее.

Другой вариант поведения. Описанное выше поведение можно менять. Есть разные виды циклов: один проверяет условие перед входом в подпрограмму, а другой сразу заходит в тело цикла. Условие он впервые проверяет уже после первой итерации.

Соответственно, если условие изначально неверно (например, «повторять, пока 0 равен 1»), первый тип цикла выполнится ноль раз, а второй – один раз. Так происходит, потому что второй тип не проверяет условие перед первой итерацией.

Итерация и итератор

Итерацию не нужно путать с другим похожим понятием – итератором. Так называется переменная-счетчик: в нее программа записывает, сколько раз цикл уже выполнился. Обычно итераторы используют в циклах, которые должны отработать определенное количество раз.

Как работает. Простейший итератор работает так: в конце каждой итерации к нему прибавляется единица. Как только значение итератора достигнет какого-то заданного порога, цикл остановится. Счет обычно начинается с нуля. Реже – с единицы.

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

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

Исключение – проход по объекту, о котором мы расскажем ниже. Там поведение итератора отличается от обычного счетчика от 0 до n.

Интерфейс итератора. Иногда можно столкнуться с понятиями «интерфейс Iterator», «протокол Iterator» и похожими. Это не совсем то же самое. Если говорить простыми словами, это объект, который умеет заниматься перечислением. Он встроен в некоторые типы данных. Но с ним можно столкнуться уже на более продвинутых уровнях изучения разработки: без знания основ сложно понять, что это такое и как работает.

Также в некоторых стандартных функциях языков есть встроенные итераторы. Они тоже работают как счетчики, но цикл разработчику писать не приходится.

Что означает «итерируемый объект»

Еще одно понятие из программирования – итерируемость. Некоторые сущности называют итерируемыми, или iterable. Если вы будете изучать какой-либо из современных языков, например, JavaScript, то с большой вероятностью столкнетесь с этим понятием.

Итерируемые объекты – это такие, содержимое которых можно пересчитать. Простейший пример – строка: в цикле можно пройти от первой ее буквы к последней. У нее конечное количество символов, и у каждого из них есть строго заданное место.

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

Необходимость проходить по таким объектам часто встречается в разработке, например, при парсинге, обработке строк или других данных. Поэтому итерируемость – важное понятие.

Интерфейс итератора, о котором мы упомянули выше, в обязательном порядке есть у итерируемых объектов. Это важное условие. Без него объект не получится пересчитать.

Итерация в проходах по объекту

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

Итератор в таких циклах по очереди принимает каждое значение из содержимого объекта – от первого к последнему. Разберем на примере.

Допустим, в цикле нужно пройти по строке «школа». Повторений будет пять. Итератор будет по очереди принимать значения «ш», «к», «о», «л», «а». После этого он дойдет до конца строки, и цикл завершится.

Такой формат удобен, потому что при работе с массивом или строкой часто бывает нужно работать с отдельными элементами из набора. Например, массив содержит множество сообщений, и каждое нужно обработать отдельно от другого. Это удобно сделать с помощью прохода по массиву в цикле.

Проходить таким образом можно только по итерируемым объектам.

Чем итерации отличаются от рекурсии

Еще один пример повторяющегося алгоритма – рекурсия. Но она работает по другому принципу. Рекурсивный и итеративный подход различаются следующим:

• итеративная подпрограмма вызывается, завершается и снова вызывается несколько раз подряд;
• рекурсивная функция вызывает сама себя, но с другими аргументами. В итоге одновременно может быть открыто несколько вложенных друг в друга подпрограмм.

У рекурсивных функций тоже есть условия для выхода, но пишутся они иначе. Если аргументы отвечают какому-то условию, функция возвращает некоторое значение и закрывается. Это значение передается в предыдущий экземпляр – и так далее. Они завершаются от внутренних к внешним.

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

Примеры задач, которые решаются итеративно

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

Циклический подсчет. Простой пример – расчет какого-нибудь математического выражения, например, факториала или n-го числа Фибоначчи. Кстати, такие задачи можно решать и рекурсивно, но часто это неоптимально с точки зрения использования памяти.

Факториал – это число, которое получается, если по очереди умножить друг на друга числа от 1 до n. Например, факториал из 5 (записывается как 5!) равен 1 * 2 * 3 * 4 * 5 = 120.

Так как умножать числа нужно несколько раз и по очереди, здесь будет уместен цикл с заданным количеством итераций. Итератор будет отсчитывать значения от 1 до n.

Кстати, итератор можно использовать при перемножении – хранить в переменной промежуточный результат и на каждом шаге умножать на итератор. Ведь он точно так же по очереди меняется от 1 до n. Правда, тогда надо сразу прописать, чтобы отсчет итератора начался с 1, а не с 0, как обычно. Иначе весь результат окажется равен 0.

Перебор массива или объекта. Представьте, что с сервера пришел большой массив строк. В каждой из них – данные по какому-то товару с сайта. Это условный упрощенный пример, на самом деле особенности передачи данных с сервера несколько сложнее.

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

На каждом шаге цикла можно выполнять заданные действия с нужным элементом. На следующем шаге те же действия выполнятся с другим элементом – и так далее до конца массива. Не нужно несколько раз писать одно и то же, все сделает программа.

Правда, в некоторых языках для такой обработки массива существуют специальные функции. С их помощью пройти и обработать итерируемый объект можно в одну строку – но такое есть не везде, и это более продвинутый уровень.

Повтор до выполнения условия. Абстрактный пример: каждый месяц количество пользователей сайта увеличивается в среднем на n процентов. Нужно проанализировать, сколько месяцев пройдет, прежде чем количество пользователей достигнет определенного числа m. Будем считать, что динамика прироста остается одинаковой.

В этом случае мы точно не знаем, сколько повторений нужно. Но задача сводится к тому, чтобы несколько раз высчитать n % от текущего количества, прибавить к текущему количеству и сравнить с пороговым числом m. На каждом шаге счетчик нужно увеличивать на 1 – один месяц. Это можно сделать итеративно.

Понадобится цикл с неопределенным количеством повторений – тот, который выполняется, пока верно или неверно какое-либо условие. Можно написать условие «повторять, пока количество пользователей не станет равно или больше m» – и программа сама повторится нужное количество раз.

Потом подпрограмма должна вернуть количество месяцев, то есть фактическое количество итераций. Кстати, цикл можно использовать повторно с разными n и m – для каждых входных данных цикл подсчитает свой результат. Соответственно, будет меняться и количество итераций.

Как часто нужно решать задачи итеративно

Решать задачи в цикле – стандартный алгоритм для многих языков. Но в коммерческой разработке этот подход не всегда применим. Например, в JavaScript считается, что лучше обходиться без перебора массивов в цикле – вместо этого советуют применять специальные встроенные функции. Но в целом итерации встречаются много где, а конкретный подход во многом зависит от языка программирования.

С итерациями человек сталкивается еще в самом начале обучения программированию. Циклы – часть базового синтаксиса практически любого языка. А без нескольких итераций цикл не получится.

Даже если впоследствии программист в основном будет работать с языком, где редко нужны циклы, знать их все равно надо. Это основа, база, которая помогает понять структуру и принцип работы с языком.