Привет, Хабр! Меня зовут Артём. Я руковожу группой Scala-разработчиков в компании "Криптонит" и веду Scalabook — русскоязычную базу знаний по Scala и функциональному программированию. В ней можно найти другие мои статьи-инструкции, а также примеры кода. В этой статье предлагаю обсудить циклы и связанные с ними спорные моменты.
Одной из первых конструкций, изучаемых в программировании, является цикл. Это даже одна из первых вещей, с которой мы сталкиваемся в жизни. Мамы ласково шепчут детям: "Не можешь заснуть? А ты мысленно посчитай овечек..." И вот вы начинаете считать: "одна овечка, две овечки, три овечки, четыре..."
Вот он — наш цикл:
var lamb = 0
while true do
println(lamb)
lamb += 1А теперь представьте, что циклы попали под санкции! Пишите вы так на своём любимом языке программирования while... и тут, бац! Ваша любимая IDE, верой и правдой прослужившая десятки лет, прошедшая вместе с вами несколько прогоревших стартапов, пару крупных корпораций, а, может быть, даже галеры (?) подло так выдаёт: "Thank you for using ‘while’. Unfortunately, we are unable to accept 'while' from Russian sources due to export policy at this time. Thank you for continuing to use ‘while’..." Теперь вы понимаете, что ощущали селебрети, когда запретили Instagram?! Да, кстати, в Scala вполне возможно на уровне компиляции запретить использование while. И ни одна душа в мире проекте не получит подсанкционный хамон while!
Чем плох while?
Рассмотрим повторяющееся вычисление:
дано исходное состояние;
выполняем проверку состояния;
если проверка успешна, то изменяем состояние (или не меняем в случае бесконечного цикла) и возвращаемся в пункт 2;
иначе возвращаем результат.
Конструкция while:
def factorialCycle(n: Int): Int = // Исходное состояние
var acc = 1 // Исходное состояние
var i = n // Исходное состояние
while i > 0 do // Проверка состояния
acc *= i // Изменение состояния
i -= 1 // Изменение состояния
acc // РезультатДавайте попробуем переписать цикл с помощью хвостовой рекурсии:
@annotation.tailrec
def factorialTailrec(n: Int, acc: Int = 1): Int = // Начальное состояние
if n <= 0 then acc // Проверка состояния и результат
else factorialTailrec(n - 1, n * acc) // Изменение состояния и возврат к проверке А если не видно разницы, то...
Давайте присмотримся: рекурсия знает своё состояние, а цикл — нет. При использовании рекурсии мы можем этим состоянием манипулировать.
Зная состояние, мы можем прервать рекурсию и когда захотим — продолжить, мы можем разбить рекурсию на части, вычисляя каждую отдельно. С циклом такой фокус не пройдет: мы либо вычисляем его полностью, либо ничего. Мы не можем его остановить, потому что потом придется все начинать сначала. У цикла неявное состояние.
Вот ещё несколько важных отличий:
Невозможность ленивых вычислений — конструкции while по своей сути строгие — они должны вычислять условие и выполнять тело цикла. Рекурсивные функции могут быть ленивыми и генерировать бесконечные структуры данных. Например, список простых чисел.
Отсутствие композиции — результат вычисления while — его побочный эффект. Трудно скомбинировать несколько циклов while в более сложную операцию, так как циклы не возвращают значений.
И даже если кто-то укажет, что в Scala под капотом у хвостовой рекурсии находится всё тот же императивный цикл, то можно ответить, что всё заканчивается байт-кодом, но это не означает, что все должны изучать Ассемблер.
Одна из самых больших проблем в программировании — чётко сформулировать задачу, поэтому появляются абстракции, понижающие уровень сложности. Кто-то опять может заметить, что в ФП абстракция абстракцией погоняет (одна эпопея с монадами чего стоит), но это, опять же, — вопрос границ. Мы ограничиваем использование — запрещаем использовать goto, чтобы сделать код надёжнее и предсказуемее. То же самое и с while с его неявным состоянием!
Так может стоит совсем отказаться от циклов и запретить while, как «вредную» конструкцию? Может быть, это следующая ступень эволюции после отхода от goto?!
goto на минималках
Кажется, что циклы были всегда и развивались вместе с языками программирования. В самых первых компьютерах программирование велось с помощью машинных кодов и ассемблеров. Циклы организовывались с помощью условных и безусловных переходов. Разработчики вручную сравнивали значения и "прыгали" на начало блока кода, если условие выполнялось. Это был "дедушка" всех циклов.
нач��ло_цикла:
... (тело цикла) ...
CMP AX, BX ; Сравнить регистр AX и BX
JNE начало_цикла ; Перейти к началу, если не равны
В конце 1950-х пришло осознание, что программы, написанные с помощью частых переходов, становятся сложными для понимания и поддержки — непредсказуемый control flow. Это привело к развитию структурного программирования. Язык Алгол (ALGOL) стал революционным. Его разработчики (среди которых были такие мэтры, как Фридрих Бауэр, Джон Бэкус, Эдсгер Дейкстра и другие) стремились создать язык, удобный для описания алгоритмов. Именно в ALGOL 60 впервые появилась чёткая и ясная конструкция цикла while. Эта конструкция стала фундаментальным прорывом. Она позволяла выражать намерение программиста ("повторять, пока истинно условие") прямо и без использования оператора перехода GOTO.
В качестве побочного эффекта это породило целую войну среди тех, кто ненавидит goto и всячески ратует за его запрет в языках программирования, и теми, кто считает использование goto оправданным — например, в качестве выхода из вложенных циклов или примитивного обработчика исключений. Не хочу вставать на чью-либо сторону, хотя сам в последний раз пользовался безусловным переходом почти двадцать лет назад (мне просто приставили пистолет к затылку), но выскажу своё мнение.
Как мне кажется, циклы возникли как ответная реакция на бездумное распространение goto, в качестве попытки упростить control flow. Возможность перехода в любую точку з��манчива, но требует от разработчика держать в голове большой контекст — это довольно сложно. Циклы резко сужают возможности goto, оставляя лишь несколько переходов: переход на следующий статус, выход из цикла (break), досрочный переход на следующую итерацию (continue).
Ключевую роль в этом процессе сыграл Эдсгер Дейкстра, опубликовавший знаменитое письмо "Go To Statement Considered Harmful", которое стало манифестом структурного программирования: давайте резко ограничим использование goto только лишь через концепцию циклов! После этого началась долгая борьба за запрет goto. В большинстве современных языков программирования goto нет: безусловный переход эволюционировал в циклы.
Рекурсия и итерация
Помимо циклов есть ещё один способ повторения действий — рекурсия. Математическая концепция рекурсии и итерации (циклов) существовала задолго до появления компьютеров. Ещё в 1930-х годах Алонзо Чёрч и Алан Тьюринг заложили теоретический фундамент вычислений, который неявно включал в себя идею повторения действий. Хотя непосредственно о циклах в этих работах не говорится, тезис Чёрча — Тьюринга устанавливает, что все вычислимые функции могут быть вычислены с помощью рекурсии (λ-исчисление Чёрча) или итерации (машины Тьюринга), подразумевая их эквивалентность в вычислительной сложности. С тех пор опубликовано много работ, доказывающих эквивалентность хвостовой рекурсии и итерации: [McCarthy J., (1960); Bird R.S. (1998); Wand M. (1980); Appel A.W. (1992)]
В функциональных языках основная конструкция для повторяющихся действий — это рекурсия, в императивных языках — итерация. В частности в Scala, компилятор автоматически преобразует хвостовую рекурсию в итерацию.
Рекурсия более чётко разделяет состояние от его изменения.
Это может быть метод:
@tailrec
def loop(начальное состояние) =
изменение состояния... или специализированный метод, типа свёртки fold, reduce и т. д.:
def fold(начальное состояние)(изменение состояния)
Итерация и рекурсия изоморфны друг другу. То есть, между итерацией и рекурсией существует взаимно однозначное соответствие. Любой алгоритм, который можно реализовать с помощью цикла (итерации), можно реализовать и с помощью рекурсии. Мы можем переписать итерацию на рекурсию и обратно.
Например, у нас есть итеративный подсчёт суммы:
def sumIter(number: Array[Int]): Int =
var sum = 0
var i = 0
while i < number.length do
sum += number(i)
i += 1
sumберём то, что находится до объявления цикла — исходное состояние — и переносим в параметры хвостовой рекурсии;
переносим условие выполнения итерации в качестве условия выхода из рекурсии;
возвращаем аккумулятор — то, что находится после всех итераций цикла;
в ином случае обновляем состояние.
def sumRec(number: Array[Int]): Int =
@annotation.tailrec
def loop(i: Int, sum: Int): Int =
if i == number.length then sum
else loop(i + 1, sum + number(i))
loop(0, 0)Это работает и в обратную сторону:
параметры рекурсии выносим в исходное состояние перед циклом;
условие выхода переносим в условие выполнение цикла;
аккумулятор переносим после цикла;
условие else — это тело цикла.
Что дальше?
Мы хотим понять и обозреть всё, но не всё нам доступно — есть определённая граница. Опытные разработчики её видят: как написано в комментарии, и goto тоже может использоваться с умом — в качестве выхода из вложенных циклов или примитивного обработчика исключений. Тоже самое и с while — опытный разработчик разберётся, когда использовать рекурсию, а когда — итерацию. Но для разработчиков, только начинающих свой путь, в качестве точки развития можно предложить чаще использовать рекурсию. К тому же, в ФП существуют свои паттерны с рекурсией, как в GoF — например, свёртка и генерация последовательностей (fold и unfold).
Об этом расскажем в одной из следующих статей, а пока… давайте запретим while! Разрешим им пользоваться только Senior Pomidor Developer-ам и прочим заслуженным личностям. Проблема while состоит в том, что он бесконечно расширяем в части своего неявного состояния, и многим разработчикам может не хватить опыта увидеть момент, когда состояние стало слишком сложным. Поэтому, если вдруг циклы попадут под санкции аналогично goto, то, может, это и к лучшему?
P.S.
А теперь без шуток: пока писал статью, я реально забыл сигнатуру while в Scala. Мне даже пришлось гуглить, как же он всё-таки пишется. А ведь когда-то я, дитя ООП, даже представить себе не мог программирование без while. Вот времена были, вот нравы…
Рекомендуемая литература:
McCarthy, J. (1960). «Recursive functions of symbolic expressions and their computation by machine» — одна из первых работ, показывающая как рекурсивные функции могут быть вычислены итеративно
Bird, R.S. (1998). «Introduction to Functional Programming using Haskell» — содержит формальные доказательства эквивалентности хвостовой рекурсии и итерации
Wand, M. (1980). «Continuation‑based program transformation strategies» — предлагает методы преобразования рекурсивных программ в итеративные с использованием продолжений (continuations)
Appel, A.W. (1992). «Compiling with Continuations» — практические аспекты преобразования рекурсии в итерацию в компиляторах
Комментарии (41)
vadimr
20.11.2025 12:53Итерация и рекурсия изоморфны друг другу. То есть, между итерацией и рекурсией существует взаимно однозначное соответствие
Только хвостовая (или, точнее, чуть более общего вида, чем хвостовая) рекурсия изоморфна итерации. Сложные виды рекурсии требуют обхода дерева и, как следствие, сохранения промежуточных состояний в стеке или другой структуре данных.
rukhi7
20.11.2025 12:53Так может стоит совсем отказаться от циклов и запретить while, как «вредную» конструкцию?
Может лучше темплейты запретить? Или вы их уже запретили вместе с классами?
el_mago
20.11.2025 12:53Не владею scala; со стороны примеры c while проще воспринимаются. Вот goto с while не привычно сравнивать, он как раз нарушал читаемость.
vadimr
20.11.2025 12:53Дело привычки. Если начинать изучение программирования с рекурсии, то она проще воспринимается (личный опыт). А если с goto, то будет проще восприниматься goto. Конечно, всё это если говорить об изоморфных случаях, то есть об одинаковой логике управления, выражаемой конструкцией while, как самой ограниченной из трёх.
while любят именно потому, что с его помощью сложнее наворотить запутанную логику.
MartianEngineer
20.11.2025 12:53Мне кажется, тут сильный разрыв между теорией и практикой. На уровне теории вычислений итерация и рекурсия взаимозаменяемы. Другое дело, как именно это реализуется в коде. Рекурсия с ветвлениями может быть сильно замороченной и ни разу не способствовать упрощению алгоритма.
vadimr
20.11.2025 12:53Код взаимосвязан с данными. По массиву (особенно фиксированной длины) яснее идти циклом, по списку (особенно мультисписку) – рекурсией.
I-AV
20.11.2025 12:53Концепция циклов тоже развивается: от императивных к декларативным, от простых циклов со счётчиками к итерационным циклам по коллекциям. В современных ЯП циклы стали безопаснее за счёт автоматического управления ресурсами. Появились асинхронные циклы (или как они правильно называются?) для работы с асинхронными потоками данных. На мой взгляд, циклы — вполне эффективная конструкция, и не стоит отказываться от них по идеологическим соображениям.
KonstantinTokar
20.11.2025 12:53Скалу запретить. Она заставляет мозг желать странного.
Далее банальность про ещё один язык и последующее решение его проблем через добавление циклов.
Tishka17
20.11.2025 12:53А можно чуть подробнее раскрыть тему
Генерации бесконечной последовательности. Как рекурсия может генерировать бесконечную последовательность если у нее есть результат? Кажется дело не в рекурсии как таковой, а в типе результата
Соединения двух циклов. Как вы хотите соединить? Вдоль или поперек? Опять же, если у вас рекурсия, вы получили результат и всё. Так же как функция с циклом вернула результат. Дальше можно вызвать вторую или нет.
vadimr
20.11.2025 12:53Генерации бесконечной последовательности. Как рекурсия может генерировать бесконечную последовательность если у нее есть результат?
У рекурсии есть результат, но этот результат не обязательно жадно вычислять.
В то время как цикл или выполнился весь, или до дальнейших вычислений мы не дошли.
Конечно, теоретически ничто не мешает придумать в каком-нибудь языке специальный ленивый цикл, но семантику такого оператора будет довольно сложно осмыслить, и это точно не простой while с одним входом и одним выходом.
Кажется дело не в рекурсии как таковой, а в типе результата
(Не обязательно конечный) список, например.
aamonster
20.11.2025 12:53Семантика давно придумана: это генераторы. И в большинстве случаев их легче воспринимать, чем рекурсию.
vadimr
20.11.2025 12:53Генератор и является формой записи ленивой рекурсии специального вида. Не очень понятно, как их можно противопоставлять друг другу.
Мне даже стало интересно, как можно объяснить действие генератора, не привлекая понятия рекурсии.
Tishka17
20.11.2025 12:53Нет, не является. В нем нет рекурсивного вызова на уровне языка. Генератор, это просто с внешним контролем перехода к следующему шагу. Смотрите:
while True: yield 1Цикл, рекурсии нет, а генерирует бесконечную последовательность единиц.
vadimr
20.11.2025 12:53Это синтаксически ошибочные операторы без контекста, который вы отрезали. А в контексте это возврат безымянного замыкания, которое содержит ленивый рекурсивный вызов (Y-комбинатор) и выполняет очередной шаг рекурсии.
Как только вы от последовательности единиц перейдёте к более осмысленному алгоритму, использующему результаты предыдущих шагов - станет более понятно, что происходит.
Кстати, этот оператор while не является классическим циклом while в смысле структурного программирования, так как у него не структурный выход (и вход). У Дейкстры бы язва обострилась при взгляде на него.
Tishka17
20.11.2025 12:53В контексте, это возврат замыкания, которое содержит созадваемый неявно рекурсивный комбинатор, который так же неявно разворачиваетмч в цикл. Но нет, это даже не обязано быть рекурсивным комбинатором, что бы это ни значило, это просто объект у которого есть Стейт и метод next
vadimr
20.11.2025 12:53Если по-простому, и если вы допишете недостающий контекст, то здесь написано:
define (gen) (cons 1 (delay (gen)))Вы можете объяснять это как-то более сложно (через мнимый цикл while, который не является циклом, труднопонимаемый оператор yield, возврат замыкания и неявный объект и его методы), но от природы вещей не уйти. Это простой как три копейки отложенный рекурсивный вызов.
Tishka17
20.11.2025 12:53У вас gen вызывается внутри gen. У меня - нет. Смотрите:
def gen(): while True: yield 1 for x in gen(): print(x)Tishka17
20.11.2025 12:53def gen(): while True: yield 1
for x in gen(): print(x)
vadimr
20.11.2025 12:53Так я ж пишу, вы (вместе с авторами языка Python) просто замаскировали рекурсивный вызов возвратом очередного шага рекурсии в виде замыкания gen.
Когда вы выполняете внутри своего gen оператор yield, то это ни что иное, как косвенный рекурсивный вызов следующего шага gen через часть внешней функции (с точки зрения семантики схемы программы, не с точки зрения реализации в питоне).
Tishka17
20.11.2025 12:53Нет там никакого рекурсивного вызова. Там просто сохраняется фрейм отдельно и дальше продолжается выполнение с того места где остановились.
В любом случае в статье речь именно про стиль написания кода, так то и рекурсия внутри превращается в цикл при оптимизации компилятором, но вы же это как-то игнорируете.
Генераторы - это закономерное расширение синтаксиса циклов, не ломающее стиль кода. В том время как рекурсия - альтернативная форма. Во что оно превращается внутри - да не важно вообще, наверняка там просто goto остаётся после всех возможных компиляций
vadimr
20.11.2025 12:53Там просто сохраняется фрейм отдельно и дальше продолжается выполнение с того места где остановились.
А чем это отличается от рекурсивного вызова и возврата?
В то время как я не слышал, чтобы в структуре управления "цикл" подразумевалось какое-то сохранение фреймов.
Посмотрите свежим взглядом, не замутнённым заморочками конкретного языка.
так то и рекурсия внутри превращается в цикл при оптимизации компилятором, но вы же это как-то игнорируете.
Не так. Рекурсия и цикл превращаются внутри в команды условного перехода, о чём Вы совершенно верно пишете ниже.
Генераторы - это закономерное расширение синтаксиса циклов, не ломающее стиль кода. В том время как рекурсия - альтернативная форма.
Очень избыточный в этом месте синтаксис языка Питон диктует такое ваше понимание. Однако для этого приходится привлечь массу дополнительных понятий и – самое главное – существенно переопределить само понятие цикла.
В то время как через рекурсию генератор выражается непосредственно. Но конкретно в Питоне, который сам по себе содержит многие полезные возможности функциональных языков программирования, именно так сделать было бы нельзя в первую очередь по той причине, что там по семантике подразумевается сохранение стека функциональных вызовов.
Однако неудобства конкретного языка для непосредственного выражения идеи не должны мешать нам рассматривать эту идею в чистом виде. Поэтому, конечно, связное изложение концепций программирования требует совместного использования разных языков.
Во что оно превращается внутри - да не важно вообще, наверняка там просто goto остаётся после всех возможных компиляций
Конечно.
Тем не менее, на питоновский оператор yield вполне можно посмотреть как на синтаксически замороченную форму косвенного рекурсивного вызова в обход обычного питоновского стека возвратов.
И да, рекурсия не равна стеку.
Tishka17
20.11.2025 12:53Рекурсия равна вызову функции самой себя. На уровне исходного кода, не на уровне результата компилчции. В приведенном мной примере этого нет ни в каком виде. Это не рекурсия.
vadimr
20.11.2025 12:53Рекурсия бывает прямая и косвенная. Вы оспариваете, что в результате действия оператора yield функция gen косвенно передаёт управление самой себе?
Тут надо более сложный генератор расписать, чтобы было более понятно. С внутренними переменными.
Tishka17
20.11.2025 12:53Тут нет косвенной рекурсии. Функция не запускается заново. Она просто приостанавливается и продолжается с того же места где остановилась. Как это реализовано внутри не важно.
vadimr
20.11.2025 12:53Вот смотрите, сколько механизмов вам пришлось использовать для объяснения работы генератора
def gen(): while True: yield 1в питоновском стиле:
Определение функции gen само по себе.
Замыкание функции gen, которое хранит состояние её внутренних переменных (в данном конкретном случае таких переменных нет, но в общем есть).
Понимание того, что gen – это не обычная функция, а специальная функция-генератор (частный случай итератора), что фактически обеспечивается реализацией особенного метода связанного с ней объекта. В связи с этим (на минуточку) – ещё само понятие объекта.
Оператор цикла.
Оператор yield, служащий для временной приостановки выполнения генератора.
Я согласен, что при известной настойчивости можно понять и запомнить такое объяснение, и сам я его тоже понимаю, так как владею языком Python. Однако сравните это с реализацией точно того же самого генератора на языке Scheme, которую я уже приводил:
(define (gen) (cons 1 (delay (gen)))) ;; cons добавляет единицу к последовательностиЗдесь нет ничего, кроме определения функции и её рекурсивного отложенного вызова. Ни один из этих двух пунктов не введён в язык специально для генератора. Так какое объяснение одного и того же понятия генератора проще, первое или второе?
Отмечу, что и скомпилированный машинный код для Scheme скорее всего будет эффективнее по той же причине простоты операционной реализации.
Tishka17
20.11.2025 12:53Нет, не надо использовать эти термины. Я мучаюсь тем, чтобы заставить вас использовать знакомые детали реализации и перейти к абстракции. Функция просто ставится на паузу. Всё. Никаких рекурсией, никаких замыканий нет. Есть функция, которую можно ставить на паузу и получать из нее данные по кусочку. А внутри функции такой же цикл как обычно, а может и не цикл.
vadimr
20.11.2025 12:53Это не абстракция, а ложная аналогия. Никакой паузы нет, все вычисления выполняются строго последовательно и непрерывно. Оператор yield точно так же немедленно влечёт своё продолжение, как и любой другой.
Tishka17
20.11.2025 12:53Возможно такая аналогия будет проще. Представьте что у вас есть отдельный поток, который крутит бесконечный цикл. На каждом вызове yield он останавливается и ждёт пока основной поток съест данные. В реальности никакого потока не создаётся, но логически это очень близко
vadimr
20.11.2025 12:53Да, именно! Благодаря замороченному синтаксису здесь возникает ложная аналогия с потоком. Хотя никакого потока на самом деле нет, всё последовательно.
Tishka17
20.11.2025 12:53Она не ложная, если представить что кроме потоков ОС есть логияеские потоки, которые синхронизированы. Просто я не хочу развивать эту терминологию, от нее в данном случае пользы мыло. Я привел этот аналог только потому что он вам будет понятен.
vadimr
20.11.2025 12:53У вас gen вызывается внутри gen. У меня - нет
Можно сказать и так (чисто синтаксисически), но тем не менее это код одного и того же генератора.
DVIsa
Изоморфны-то они изоморфны, а вот создавать копию состояния для каждого вызова может быть, мягко говоря, не очень удобно. Плюс читабельность кода под вопросом. Ну например перемножаете Вы две большие матрицы...