Цикл (программирование)

Цикл— разновидность управляющей конструкции ввысокоуровневых языках программирования, предназначенная для организации многократного исполнения набораинструкций. Также циклом может называться любая многократно исполняемая последовательность инструкций, организованная любым способом (например, с помощьюусловного перехода).
Последовательность инструкций, предназначенная для многократного исполнения, называетсятелом цикла. Единичное выполнение тела цикла называетсяитерацией.Выражение, определяющее, будет в очередной раз выполняться итерация или цикл завершится, называетсяусловием выходаилиусловием окончания цикла(либоусловием продолженияв зависимости от того, как интерпретируется его истинность — как признак необходимости завершения или продолжения цикла).Переменная, хранящая текущий номер итерации, называетсясчётчиком итерацийцикла или простосчётчиком цикла. Цикл не обязательно содержит счётчик, счётчик не обязан быть один — условие выхода из цикла может зависеть от нескольких изменяемых в цикле переменных, а может определяться внешними условиями (например, наступлением определённого времени), в последнем случае счётчик может вообще не понадобиться.
Исполнение любого цикла включает первоначальную инициализацию переменных цикла, проверку условия выхода, исполнение тела цикла и обновление переменной цикла на каждой итерации. Кроме того, большинство языков программирования предоставляет средства для досрочного управления циклом, например, операторы завершения цикла, то есть выхода из цикла независимо от истинности условия выхода (в языкеСи—break) и операторы пропуска итерации (в языке Си —continue).
Иногда в программах используются циклы, выход из которых не предусмотрен логикой программы. Такие циклы называются безусловными, или бесконечными. Специальных синтаксических средств для создания бесконечных циклов, ввиду их нетипичности, языки программирования не предусматривают, поэтому такие циклы создаются с помощью конструкций, предназначенных для создания обычных (илиусловных) циклов. Для обеспечения бесконечного повторения проверка условия в таком цикле либо отсутствует (если позволяет синтаксис, как, например, в циклеLOOP ... END LOOPязыкаАда), либо заменяется константным значением (while true do ...вПаскале). В языкеСиспользуется циклfor(;;)с незаполненными секциями или циклwhile (1).
Цикл с предусловием — цикл, который выполняется, пока истинно некоторое условие, указанное перед его началом. Это условие проверяетсядовыполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется операторомwhile, отсюда его второе название — while-цикл.
На языке Pascal цикл с предусловием имеет следующий вид:
На языкеСи:
Цикл с постусловием — цикл, в котором условие проверяетсяпослевыполнения тела цикла. Отсюда следует, что теловсегда выполняетсяхотя бы один раз. В языке Паскаль этот цикл реализуетоператорrepeat..until; в Си —do…while.
На языке Pascal цикл с постусловием имеет следующий вид::
На языке Си:
В трактовке условия цикла с постусловием в разных языках есть различия. В Паскале и языках, произошедших от него, условие такого цикла трактуется какусловие выхода(цикл завершается, когда условие истинно, в русской терминологии такие циклы называют ещё «цикл до»), а в Си и его потомках — какусловие продолжения(цикл завершается, когда условие ложно, такие циклы иногда называют «цикл пока»).
Если в языке не предусмотрен отдельный оператор цикла с постусловием, то его легко реализовать как цикл с предусловием с командой досрочного выхода. Например, в Python:
Цикл с выходом из середины — наиболее общая форма условного цикла. Синтаксически такой цикл оформляется с помощью трёх конструкций: начала цикла, конца цикла и команды выхода из цикла. Конструкция начала маркирует точку программы, в которой начинается тело цикла, конструкция конца — точку, где тело заканчивается. Внутри тела должна присутствовать команда выхода из цикла, при выполнении которой цикл заканчивается и управление передаётся на оператор, следующий за конструкцией конца цикла. Естественно, чтобы цикл выполнился более одного раза, команда выхода должна вызываться не безусловно, а только при выполнении условия выхода из цикла.
Принципиальным отличием такого вида цикла от рассмотренных выше является то, что часть тела цикла, расположенная после начала цикла и до команды выхода, выполняется всегда (даже если условие выхода из цикла истинно при первой итерации), а часть тела цикла, находящаяся после команды выхода, не выполняется при последней итерации.
Легко видеть, что с помощью цикла с выходом из середины можно легко смоделировать и цикл с предусловием (разместив команду выхода в начале тела цикла), и цикл с постусловием (разместив команду выхода в конце тела цикла).
Часть языков программирования содержит специальные конструкции для организации цикла с выходом из середины. Так, в языкеАдадля этого используется конструкцияLOOP ... END LOOPи команда выходаEXITилиEXIT WHEN:
Здесь внутри цикла может быть любое количество команд выхода обоих типов. Сами команды выхода принципиально не различаются, обычноEXIT WHENприменяют, когда проверяется только условие выхода, а простоEXIT— когда выход из цикла производится в одном из вариантов сложного условного оператора.
В тех языках, где подобных конструкций не предусмотрено, цикл с выходом из середины может быть смоделирован с помощью любого условного цикла и оператора досрочного выхода из цикла (такого, какbreakв Си, exit в Турбо Паскале и т. п.), либо операторабезусловного переходаgoto.
Цикл со счётчиком — цикл, в котором некотораяпеременнаяизменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз. В большинстве процедурных языков программирования реализуется операторомfor, в котором указывается счётчик (так называемая «переменная цикла»), требуемое количество проходов (или граничное значение счётчика) и, возможно, шаг, с которым изменяется счётчик. Например, в языкеОберон-2такой цикл имеет вид:
здесь v — счётчик, b — начальное значение счётчика, e — граничное значение счётчика, s — шаг).
Неоднозначен вопрос о значении переменной по завершении цикла, в котором эта переменная использовалась как счётчик. Например, если в программе на языке Паскаль встретится конструкция вида:
возникает вопрос: какое значение будет в итоге присвоено переменнойk: 9, 10, 100, может быть, какое-то другое? А если цикл завершится досрочно? Ответы зависят от того, увеличивается ли значение счётчика после последней итерации и не изменяет ли транслятор это значение дополнительно. Ещё один вопрос: что будет, если внутри цикла счётчику будет явно присвоено новое значение? Различные языки программирования решают данные вопросы по-разному. В некоторых поведение счётчика чётко регламентировано. В других, например, в том же Паскале, стандарт языка не определяет ни конечного значения счётчика, ни последствий его явного изменения в цикле, но не рекомендует изменять счётчик явно и использовать его по завершении цикла без повторной инициализации. Программа на Паскале, игнорирующая эту рекомендацию, может давать разные результаты при выполнении на разных системах и использовании разных трансляторов.
Радикально решён вопрос в языкахАдаиKotlin: счётчик считается описанным в заголовке цикла, и вне его просто не существует. Даже если имя счётчика в программе уже используется, внутри цикла в качестве счётчика используется отдельная переменная. Счётчику запрещено явно присваивать какие бы то ни было значения, он может меняться только внутренним механизмом оператора цикла.
В результате конструкция на Аде:
И на Котлине:
внешне аналогичная вышеприведённому циклу на Паскале, трактуется однозначно: переменнойkбудет присвоено значение 100, поскольку переменнаяi, используемаявнеданного цикла, не имеет никакого отношения к счётчикуi, который создаётся и изменяетсявнутри цикла. Подобное обособление счётчика удобно и безопасно: не требуется отдельное описание для него и минимальна вероятность случайных ошибок, связанных со случайным разрушением внешних по отношению к циклу переменных. Если программисту требуется включить в готовый код цикл со счётчиком, то он может не проверять, существует ли переменная с именем, которое он выбрал в качестве счётчика, не добавлять описание нового счётчика в заголовок соответствующей процедуры, не пытаться использовать один из имеющихся, но в данный момент «свободных» счётчиков. Он просто пишет цикл с переменной-счётчиком, имя которой ему удобно, и может быть уверен, что никакой коллизии имён не произойдёт.
Цикл со счётчиком всегда можно записать как условный цикл, перед началом которого счётчику присваивается начальное значение, а условием выхода является достижение счётчиком конечного значения; к телу цикла при этом добавляется оператор изменения счётчика на заданный шаг. Однако специальные операторы цикла со счётчиком могут эффективнее транслироваться, так как формализованный вид такого цикла позволяет использовать специальные процессорные команды организации циклов.
Никлаус Виртодно время называл цикл со счётчиком «маргинальным», утверждая, что такая конструкция является излишней и должна быть исключена из синтаксиса языков программирования как несистемная. В соответствии с этим представлением в языке программированияОберонцикла со счётчиком не было. Однако в языкеОберон-2, созданном Виртом и Мёссенбёком в развитие Оберона, цикл со счётчикомFORпоявился снова в интересах практического удобства использования.
В некоторых языках, например,Сии других, произошедших от него, циклfor, несмотря насинтаксическую формуцикла со счётчиком, в действительности является циклом с предусловием. То есть в Си конструкция цикла:
фактически представляет собой другую форму записи конструкции:
То есть в конструкцииforсначала пишется произвольное предложение инициализации цикла, затем — условие продолжения и, наконец, выполняемая после каждого тела цикла некоторая операция (это не обязательно должно быть изменение счётчика; это может быть правкауказателяили какая-нибудь совершенно посторонняя операция). Для языков такого вида вышеописанная проблема решается очень просто: переменная-счётчик ведёт себя совершенно предсказуемо и по завершении цикла сохраняет своё последнее значение.
Ещё одним вариантом цикла является цикл, задающий выполнение некоторой операции для объектов из заданного множества, без явного указания порядка перечисления этих объектов. Такие циклы называютсясовместными(а такжециклами по коллекции,циклами просмотра) и представляют собой формальную запись инструкции вида: «Выполнить операцию X для всех элементов, входящих во множество M». Совместный цикл, теоретически, никак не определяет, в каком порядке операция будет применяться к элементам множества, хотя конкретные языки программирования, разумеется, могут задавать конкретный порядок перебора элементов. Произвольность даёт возможность оптимизации исполнения цикла за счёт организации доступа не в заданном программистом, а в наиболее выгодном порядке. При наличии возможности параллельного выполнения нескольких операций возможно дажераспараллеливание выполнениясовместного цикла, когда одна и та же операция одновременно выполняется на разных вычислительных модулях для разных объектов, при том, что логически программа остаётся последовательной.
Совместные циклы имеются в некоторых языках программирования (C#,Eiffel,Java,JavaScript,Perl,Python,PHP,LISP,Tclи др.) — они позволяют выполнять цикл по всем элементам заданнойколлекции объектов. В определении такого цикла требуется указать только коллекцию объектов и переменную, которой в теле цикла будет присвоено значение обрабатываемого в данный момент объекта (или ссылка на него). В различных языках программирования синтаксис оператора различен:
C++:
C#:
Delphi:
Perl(строгий порядок «от первого до последнего»):
Eiffel:
Java:
JavaScript:
PHP:
Visual Basic.NET:
Windows PowerShell:
или
Python
Ruby
Многие языки программирования, имеющие в своём синтаксисе циклические конструкции, имеют также специфические команды, позволяющие нарушить порядок работы этих конструкций: команду досрочного выхода из цикла и команду пропуска итерации.
Команда досрочного выхода применяется, когда необходимо прервать выполнение цикла, в котором условие выхода ещё не достигнуто. Такое бывает, например, когда при выполнении тела цикла обнаруживается ошибка, после которой дальнейшая работа цикла не имеет смысла.
Команда досрочного выхода обычно называетсяEXITилиbreak, а её действие аналогично действию команды безусловного перехода (goto) на команду, непосредственно следующую за циклом, внутри которого эта команда находится. Так, в языке Си два нижеприведённых цикла работают совершенно одинаково:
В обоих случаях, если в теле цикла выполнится условие <ошибка>, будет произведён переход на операторы, обозначенные как «продолжение программы». Таким образом, оператор досрочного выхода из цикла, по сути, просто маскирует безусловный переход, однако использование break предпочтительнее, чем goto, поскольку поведение break чётко задано языком, потенциально менее опасно (нет, например, вероятности ошибиться с положением или названием метки). Кроме того, явный досрочный выход из цикла не нарушает принципов структурного программирования.
Обычный оператор досрочного выхода прерывает работу того цикла, в котором он непосредственно находится. В ряде языков программирования функциональность этого оператора расширена, он позволяет выходить из нескольких вложенных циклов (см. ниже). В таких случаях цикл, из которого требуется выйти, помечается меткой, а в операторе досрочного выхода указывается эта метка.
Данный оператор применяется, когда в текущей итерации цикла необходимо пропустить все команды до конца тела цикла. При этом сам цикл прерываться не должен, условия продолжения или выхода должны вычисляться обычным образом.
В языке Си и его языках-потомках в качестве команды пропуска итерации используется операторcontinueв конструкции цикла. Действие этого оператора аналогично безусловному переходу на строку внутри тела цикла, следующую за последней его командой. Например, код на Си, находящий сумму элементов массива и сумму всех положительных элементов массива, может иметь следующий вид:
Из второго фрагмента ясно видно, как работаетcontinue: он просто передаёт управление за последнюю команду тела цикла, пропуская выполнение команды суммирования, если очередной элемент массива не удовлетворяет условию. Таким образом, в sum_pos накапливается сумма лишь положительных элементов массива.
С точки зрения структурного программирования команды досрочного выхода из цикла и пропуска итерации являются избыточными, поскольку их действие может быть легко смоделировано чисто структурными средствами. Более того, по мнению ряда теоретиков программирования (в частности, Эдсгера Дейкстры), сам факт использования в программе неструктурных средств, будь то классический безусловный переход или любая из его специализированных форм, таких как break или continue, является свидетельством недостаточно проработанного алгоритма решения задачи.
Однако на практике код программы часто является записью уже имеющегося, ранее сформулированного алгоритма, перерабатывать который нецелесообразно по чисто техническим причинам. Попытка заменить в таком коде команду досрочного выхода на структурные конструкции часто оказывается неэффективной или громоздкой. Например, вышеприведённый фрагмент кода с командойbreakможет быть записан так:
Легко убедиться, что фрагмент будет работать аналогично предшествующим, разница лишь в том, что в месте проверки на ошибку вместо непосредственного выхода из цикла устанавливается флаг досрочного выхода, который проверяется позже в штатном условии продолжения цикла. Однако для отказа от команды досрочного выхода пришлось добавить в программу описание флага и вторую ветвь условного оператора, к тому же произошло «размытие» логики программы (решение о досрочном выходе принимается в одном месте, а выполняется в другом). В результате программа не стала ни проще, ни короче, ни понятнее.
Несколько иначе обстоит дело с командой пропуска итерации. Она, как правило, очень легко и естественно заменяется на условный оператор. Например, приведённый выше фрагмент суммирования массива можно записать так:
Как видим, достаточно было заменить проверяемое условие на противоположное и поместить заключительную часть тела цикла в условный оператор. Можно заметить, что программа стала короче (за счёт удаления команды пропуска итерации) и одновременно логичнее (из кода непосредственно видно, что суммируются положительные элементы).
Кроме того, использование команды пропуска итерации в цикле с условием (while-цикле) может также спровоцировать неочевидную ошибку: если тело цикла, как это часто бывает, завершается командами изменения переменной (переменных) цикла, то команда пропуска итерации пропустит и эти команды тоже, в результате чего (в зависимости от условия, по которому происходит пропуск) может произойти зацикливание или не соответствующий алгоритму повтор итерации. Так, если заменить в вышеприведённом примере цикл for на while, получится следующее:
Несмотря на свою ограниченную полезность и возможность замены на другие языковые конструкции, команды пропуска итерации и, особенно, досрочного выхода из цикла в отдельных случаях оказываются крайне полезны, именно поэтому они сохраняются в современных языках программирования.
Существует возможность организовать цикл внутри тела другого цикла. Такой цикл будет называтьсявложенным циклом. Вложенный цикл по отношению к циклу, в тело которого он вложен, будет именоватьсявнутренним циклом, и наоборот, цикл, в теле которого существует вложенный цикл, будет именоватьсявнешнимпо отношению к вложенному. Внутри вложенного цикла, в свою очередь, может быть вложен ещё один цикл, образуя следующийуровень вложенностии так далее. Количество уровней вложенности, как правило, не ограничивается.
Полное число исполнений тела внутреннего цикла не превышает произведения числа итераций внутреннего и всех внешних циклов. Например, взяв три вложенных друг в друга цикла, каждый по 10 итераций, получим 10 исполнений тела для внешнего цикла, 100 для цикла второго уровня и 1000 в самом внутреннем цикле.
Одна из проблем, связанных с вложенными циклами — организация досрочного выхода из них. Во многих языках программирования есть оператор досрочного завершения цикла (breakв Си,exitв Турбо Паскале,lastвPerlи т. п.), но он, как правило, обеспечивает выход только из цикла того уровня, откуда вызван. Вызов его из вложенного цикла приведёт к завершению только этого внутреннего цикла, внешний же цикл продолжит выполняться. Проблема может показаться надуманной, но она действительно иногда возникает при программировании сложной обработки данных, когда алгоритм требует немедленного прерывания в определённых условиях, наличие которых можно проверить только в глубоко вложенном цикле.
Решений проблемы выхода из вложенных циклов несколько.
В теории программирования известна ещё одна, принципиально отличающаяся от «классических», форма циклической конструкции, получившая название «цикл Дейкстры», по имениЭдсгера Дейкстры, впервые её описавшего. В классическом дейкстровском описании такой цикл выглядит следующим образом:
Здесьdo— маркер начала конструкции цикла,od— маркер завершения конструкции цикла, Pi—i-еохраняющее условие(логическое выражение, которое может иметь значение «истинно» или «ложно»), Si—i-яохраняемая команда. Цикл состоит из одной или несколькихветвей(охраняемых выражений), каждая из которых представляет собой пару из охраняющего условия (или, коротко, «охраны») и охраняемой команды (понятно, что в реальности команда может быть сложной).
При выполнении цикла Дейкстры в каждой итерации происходит вычисление охраняющих условий. Если хотя бы одно из них истинно, выполняется соответствующая охраняемая команда, после чего начинается новая итерация (если истинны несколько охраняющих условий, выполняется только одна охраняемая команда). Если все охраняющие условия ложны, цикл завершается. Нетрудно заметить, что цикл Дейкстры с одним охраняющим условием и одной охраняемой командой представляет собой, по сути, обычный цикл с предусловием (цикл «пока»).
Хотя цикл Дейкстры был изобретён ещё в 1970-х годах, специальных конструкций для его создания в языках программирования не содержится. Единственным исключением стал недавно созданныйОберон-07— первый реальный язык программирования, явно поддерживающий цикл с несколькими охраняемыми ветвями. Впрочем, цикл Дейкстры может быть без больших затруднений смоделирован с помощью традиционных конструкций структурных языков программирования. Вот пример его реализации одним из возможных способов на языке Ада:
Здесь P1—Pn — охраняющие условия, а S1—Sn — соответствующие охраняемые команды.
Цикл Дейкстры удобен при реализации некоторых специфических повторяющихся вычислений, которые неудобно описывать с помощью более традиционных циклических конструкций. Например, этим циклом естественно представляетсяконечный автомат— каждая ветвь соответствует одному состоянию автомата, охраняемые условия строятся так, чтобы в текущей итерации выбиралась ветвь, соответствующая текущему состоянию автомата, а код охраняемой команды обеспечивает выполнение вычислений в текущем состоянии и переход в следующее (то есть такое изменение переменных, после которого на следующей итерации будет истинным охраняющее условие нужной ветви).
Легко видеть, что цикл Дейкстры не содержит явного условия продолжения или выхода, что не всеми теоретиками программирования рассматривается как благо. Поэтому была предложена усложнённая конструкция цикла Дейкстры, получившая название «цикл-'паук'». В той же нотации она выглядит следующим образом:
Здесь после маркераoutдобавленыветви завершения, состоящие из условий выхода Qiи команд завершения Ti. Кроме того, добавлена ветвь альтернативного завершенияelseс командой E.
Цикл-'паук' выполняется так:
Структура цикла-'паука' позволяет предельно строго описать условия выполнения цикла. Согласно теоретическим положениям, ветвь альтернативного завершения не должна использоваться в качестве одного из вариантов корректного прекращения работы цикла (все такие варианты должны быть оформлены в виде соответствующих ветвей завершения с явным условием), она служит только для того, чтобы отследить ситуацию, когда по каким-то причинам цикл начал выполняться нештатно. То есть команда альтернативного завершения может лишь анализировать причины ошибки и представлять результаты анализа.
Хотя явной поддержки на уровне синтаксиса для этого цикла не существует ни в одном языке программирования, цикл-'паук', как и цикл Дейкстры, может быть смоделирован с помощью традиционных структурных конструкций.
эквивалентными преобразованиями исходного кода:
компилятором: