что такое итерационный процесс
Функциональное программирование с точки зрения EcmaScript. Рекурсия и её виды
Сегодня мы продолжим наши изыскания на тему функционального программирования в разрезе EcmaScript, на спецификации которого основан JavaScript. В предыдущих статьях цикла были рассмотрены следующие темы:
Рекурсия
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее применение находит в математике и информатике.
Применительно к программированию под рекурсией подразумевают процессы, которые вызывают сами себя в своём теле. Рекурсивная функция имеет несколько обязательных составляющих:
Выделим характерные составляющие рекурсивной функции. Терминальное условие
и правило движения по рекурсии
Важно осознавать, что рекурсия это не какая-то специфическая фича JS, а техника очень распространённая в программировании.
Рекурсивный и итеративный процессы
Рекурсию можно организовать двумя способами: через рекурсивный процесс или через итеративный.
Рекурсивный процесс мы с вами уже видели:
Итеративное решение задачи о факториале выглядело бы так:
Оба этих варианта это рекурсия. В обоих решениях есть характерные для рекурсии черты: терминальное условие и правило движения по рекурсии. Давайте разберём их отличия.
Рекурсивный процесс на каждом шаге запоминает действие. которое надо сделать. Дойдя до термального условия, он выполняет все запомненные действия в обратном порядке. Поясним на примере. Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вглубь больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.
Выглядит это примерно так:
Как видите, основная идея рекурсивного процесса — откладывание вычисления до конца.
Такой процесс порождает изменяемое во времени состояние, которое хранится «где-то» снаружи текущего вызова функции.
Думаю, вы помните, что в первой статье из цикла о Функциональном программировании мы говорили о важности имутабельности и отсутствия состояния. Наличие состояния порождает много проблем, с которыми не всегда легко справится.
Итеративный процесс отличается от рекурсивного фиксированным количеством состояний. На каждом своём шаге итеративный процесс считает всё, что может посчитать, поэтому каждый шаг рекурсии существует независимо от предыдущего.
Думаю, очевидно, что итеративный процесс потребляет меньше памяти. Следовательно, всегда при создании рекурсии следует использовать его. Единственное исключение: если мы не можем посчитать значение до достижения термального условия.
Древовидная рекурсия
Многие считают, что деревья и работа с ними это что-то очень заумное, сложное и не понятное простым смертным. На самом деле это не так. Любая иерархическая структура может быть представлена в виде дерева. Даже человеческое мышление подобно дереву.
Чтобы лучше понять древовидную рекурсию разберём простой и популярный пример — числа Фибоначчи.
Чи́сла Фибона́ччи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS), в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Математически довольно просто сформулировать описание (а ведь декларативное программирование и есть описание) данной последовательности:
Теперь давайте перейдём от математики к логическим рассуждениям(нам ведь нужно программную логику написать). Для вычисления fib(5) нам придётся вычислить fib(4) и fib(3). Для вычисления fib(4) нам придётся вычислить fib(3) и fib(2). Для вычисления fib(3) нам придётся вычислить fib(2) и так до тех пор пока мы не дойдём до известных значений (1) и (2) в нашей математической модели.
На какие мысли нас должны навести наши рассуждения? Очевидно, мы должны использовать рекурсию. Термальное условие можно сформулировать как n
Итеративный процесс — Основы программирования
Визуализация итеративного процесса
Рекурсия vs. какой-то процесс
Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.
пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину.
Теперь на секунду забудем про рекурсию, и просто подумаем про компьютеры. Для выполнения задач компьютерам нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — это процесс. Простой цикл, выводящий на экран десять раз число «42» — это процесс. Некоторые задачи можно решать рекурсивно, то есть в инструкциях использовать эту концепцию, когда что-то является частью самого себя. В частности, функция может быть частью самой себя, то есть вызывать саму себя.
Есть два метода решения задач с использованием рекурсии: рекурсивный процесс и итеративный процесс. Рекурсия в них не отличается: в каждом из подходов функция вызывает саму себя, рекурсивно. Отличаются способы использования идеи рекурсии.
Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.
В чем отличие итеративного процесса от рекурсивного?
Главная фишка в аккумуляторе или, иными словами, в запоминании.
Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.
тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел
Рекурсивный процесс — это процесс с отложенным вычислением.
Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг.
тут видно, что использования памяти не растет
Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится 🙂
Итеративный процесс это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница — просто обычный день, но последний.
Tail call optimization
Отмотаем назад и рассмотрим во взаимосвязи два утверждения относительно рекурсивных функций, использующих итеративный процесс:
Хвостовая рекурсия (и её оптимизация) широко используется при написании программ на функциональных языках программирования.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты.
Что такое итерационный процесс
Итерации — секрет прекрасных результатов
Аудио перевод статьи
Аудио перевод статьи
Когда я начал работать дизайнером, я не мог поверить в свою удачу.
Мне платили за то, чтобы я исследовал, экспериментировал и пробовал разные вещи. Все, что мне нужно было делать, продолжать до тех пор, пока все кусочки не сложатся в единую картину.
Тогда я не понимал, что такой метод работы называется итерациями.
Итерации — феноменальная техника. Ее очень просто изучить, и она позволяет извлекать выгоду из всего опыта и знаний, которые вы приобретаете. Все знают о ней — но мало кто пользуется.
Вы сразу увидите результат. Неважно, являетесь ли вы лишь начинающим в этой области или уже опытным профессионалом. Работа итерациями всегда поможет вам добиваться лучших результатов.
Из этой статьи вы получите несколько важных советов о том, как сделать ваши итерации максимально эффективными. Вы также узнаете, почему указанный метод работает и какие преимущества он вам дает.
Начало работы итерациями
По существу, работа итерациями предполагает повторение процесса с измененными переменными для получения различных результатов. Это означает пытаться снова и снова.
Вы либо начинаете с нуля, либо используете предыдущий результат в качестве отправной точки. Эти два подхода формируют итерационную матрицу.
Горизонтальные итерации
Горизонтальные итерации означают движение вширь. Ваша цель — исследовать различные подходы или идеи, каждый раз начиная с нуля. Например, когда вы хотите представить несколько вариантов дизайна команде или клиенту.
Делайте итерации отличными друг от друга. Покажите разные направления, взгляды или подходы к решению задачи. В каждой итерации сфокусируйтесь на конкретном выводе, полученном в результате ваших исследований, использования метода Jobs to be done или персон.
Цель горизонтальных итераций —это получение общей картины. Не зацикливайтесь на деталях.
Вертикальные итерации
Вертикальные итерации предполагают движение вглубь. Ваша цель — найти лучшую версию конкретной идеи. Начиная с результатов предыдущей итерации, вы меняете отдельные детали, пока не будете удовлетворены результатом.
Если какая-то идея не работает, пора перейти к другой (по горизонтальной оси) и снова углубиться.
Цель вертикальных итераций — достичь совершенства, то есть добавить изыски и детали, которые сделают пользовательский опыт прекрасным.
5 важных советов по работе итерациями
Используйте как основу данные и вдохновляющие примеры
Работа итерациями должна быть основана на информации. Это означает, что вы исследуете, собираете вдохновляющие примеры и обратную связь и используете их как основу для своей работы.
В процессе работы у вас могут появиться новые идеи — это здорово. Это также означает, что вам необходимо провести дополнительные исследования для проверки новой идеи.
Это часть процесса работы итерациями. Он состоит из достижения результатов, а также исследований, необходимых для этого.
Сфокусируйтесь на том, чтобы достичь результата, а не совершенства
Итерации начинаются как наброски. Их цель — представить идею таким образом, чтобы можно было принять решение. Чем быстрее вы доведете итерации до этапа, на котором станет возможным принятие решений, тем лучше.
Вот почему, когда вы начинаете первую итерацию, вы должны максимально быстро добавить все составляющие вашего решения. Это MVP (минимально жизнеспособный продукт) вашей идеи, черновик. Вы можете подумать о деталях позднее.
Не принимайте близко к сердцу
Итерации — это инструмент открытий, изучения и развития. В конце концов вы все равно выбросите большую часть своих наработок. Подход будет максимально эффективным, если вы не станете тратить слишком много времени на каждую отдельную итерацию. Если вы слишком сильно привяжетесь к своим идеям, вам будет трудно заметить ошибки и вносить изменения. Всегда дистанцируйтесь от вашей работы.
Не торопитесь
Итерации существуют не только в вашей практической работе, но и в мыслительном процессе. Решение любых проблем — это, прежде всего, работа мозга. Одна из прекрасных особенностей нашего мозга заключается в том, что он продолжает работать над решением проблем, даже когда мы не осознаем этого и не думаем о них намеренно.
Вот почему на следующий день проблема воспринимается совершенно по-другому. Воспользуйтесь механизмом “пассивного” решения проблем, запланировав свободное время между итерациями. Потратьте на каждую итерацию несколько дней либо отправьтесь на прогулку между ними.
Работайте вместе, смешивайте и сочетайте идеи
Совместная с коллегами работа итерациями может быть еще более эффективной. После первой сессии вы можете пересмотреть свои идеи и смешать их с тем, что придумали ваши коллеги. Никто не будет зол на вас за это, при условии, что вы укажете их авторство. Возможности команды всегда больше, чем возможности отдельного человека.
Почему работа итерациями эффективна
Результаты сложно измерить количественно, особенно это касается творческого труда. Чтобы прочувствовать, насколько эффективной является работа итерациями, вам необходимо самостоятельно попробовать этот подход либо внимательно понаблюдать за тем, как кто-то его применяет. Лучшее, что я могу сделать — это поделиться своими наблюдениями.
В целом, в основе итераций лежит идея эволюции. Добавление новой версии поверх последней позволяет вам стабильно работать над улучшением результата. Вместо того, чтобы пытаться добиться совершенного решения с первой попытки, вы работаете циклами.
Ваша первая идея никогда не бывает лучшей
Мозгу требуется время, чтобы обдумать проблемы, которые вы пытаетесь решить. Как и в спорте, разминка поможет вам добиться максимальной продуктивности.
Нам свойственно сразу обращаться к самому очевидному решению. Это обычно что-то, что мы видели раньше. Чтобы найти новую или уникальную идею, нам надо сначала хорошо проанализировать проблему. Осознав имеющиеся ограничения и возможности, мы полностью готовы к решению проблемы.
Идеи блокируют ваш мозг
В психологии существует волшебное число 7, также известное как закон Миллера. Эта теория предполагает, что человек может в среднем удерживать в краткосрочной памяти 7 ± 2 объекта.
Это правило применимо и к идеям. Вам необходимо вытащить из своей головы одну, чтобы освободить место для новой. Лучший способ очистить свой разум — реализовать свои идеи. В этом случае вы их не забудете, и ваш разум сможет освободиться.
В теории все кажется лучше
Возможно, вы уже сталкивались с этим раньше: идея кажется великолепной в вашем воображении, однако когда вы пытаетесь ее реализовать, она не работает.
Хотя проблема может заключаться в недостатке навыков, существует и другое объяснение.
Когда вы обдумываете идеи, мозг игнорирует те составляющие, которые не работают. В этот момент нет ничего невозможного, никаких рамок. Однако как только вы попытаетесь воплотить свою идею в жизнь, вы столкнетесь с ограничениями, которые невозможно будет игнорировать.
Чем раньше вы поймете, что может не сработать, тем быстрее вы исправите это или разработаете новое решение.
Погружение в сам процесс освобождает от зацикленности на результате
Работа итерациями может избавить вас от лишнего стресса. Гораздо проще пробовать, когда то, что вы делаете, не является финальной версией. Так уж совпало, что когда на нас не давит необходимость сделать все идеально, мы зачастую добиваемся более высоких результатов.
Только в том случае, если мы позволим себе провалиться, мы сможем рискнуть, выбрав сумасшедшую идею, которая в конце концов позволит нам изменить правила игры в свою пользу.
Не испытывая давления, мы можем свободно мыслить и преодолеть “страх чистого листа”.
Преимущества работы итерациями
Готовность в любое время показать свои идеи и рассказать о них
Когда вы работаете итерациями, у вас всегда есть какой-то вариант вашей идеи, который вы готовы обсудить.
Он может быть не окончательным, но у вас все равно есть, что показать своим коллегам и заинтересованным сторонам. Наброски могут быть грубыми, но, если вы следуете моим советам, они будут достаточно завершенными, чтобы продемонстрировать идею и намерения понятным образом. Это поможет людям получить общее представление.
Такая предварительная версия идеи позволит вам на раннем этапе получить поддержку, ценную обратную связь и обсудить варианты решения с вашей командой.
Отличное соотношение усилий и результатов
Работа итерациями позволяет вам сфокусироваться на важном. Неэффективные идеи сразу же отклоняются, без лишних затрат времени и усилий.
Перспективные идеи улучшаются до тех пор, пока они не станут идеальными. Участие заинтересованных сторон в процессе итераций позволит вам заручиться их поддержкой на раннем этапе. Это снизит риск попасть в ситуацию, когда вы потратите время и силы на реализацию идеи, которую не сможете продать.
Уровень вашего мастерства не имеет значения
Как я уже упоминал в начале статьи: каждый может использовать метод итераций и выиграть от этого.
Вам не обязательно быть экспертом. Фактически, если вы новичок, ваши наставники или руководители, вероятно, попросят вас работать итерациями. Вы можете начать использовать этот метод уже сегодня и он немедленно принесет вам пользу.
Итерации делают совместную работу проще
У некоторых людей отлично получается начинать проекты, другие — хороши в доработке мелких деталей. Совместная работа итерациями позволяет каждому делать то, в чем он наиболее успешен.
Дизайнер разрабатывает проект лендинга — чего не может сделать команда по маркетингу. А последняя, в свою очередь, делает текст на сайте более эффективным и может предложить ряд изменений для повышения конверсии.
Итерации позволяют достичь успеха
Что мне нравится в методе работы итерациями, так это то, что вы можете использовать его для решения разных задач. Дизайн, написание кода, статей, кулинария, составление распорядка дня, развитие навыков общения и т.д.
Итерации даже превратились в бизнес-философию. Контент Википедии, например, становится высококачественным за счет прохождения через бесконечные итерации. Это также верно и для карт, которые может дополнять любой желающий.
Я практически всегда использую метод итераций в своей профессиональной деятельности, включая работу над этим веб-сайтом. Вместо того, чтобы за месяц разработать одну основную версию, я выпускаю небольшие обновления каждый раз, когда вношу какие-то изменения. Больше всего в таком подходе мне нравится то, что как только я что-то меняю, моя аудитория сразу же получает пользу.
Резюме
Подводя итог, можно сказать, что работа итерациями — это метод, который вы можете начать применять уже сегодня, чтобы немедленно почувствовать его эффективность. Итерации помогают усовершенствовать ваш рабочий процесс, снижая риск потери времени и усилий.
Это отличный инструмент, который каждый может начать использовать уже сегодня.
Итеративный процесс — Введение в программирование
В видео есть неточность: в формуле вычисления факториала и в коде, который на ней основан, не учитывается, что для 0 (нуля) тоже можно вычислить факториал — он равен 1 (единице). Исправленный код есть ниже в конспекте.
Транскрипт урока
Рекурсию можно использовать разными способами: тот, который мы рассматривали в предыдущем уроке, называется рекурсивным процессом. Сегодняшний урок будет более понятен, если вы уже разобрались с предыдущей темой и выполнили упражнение.
Другой способ использования рекурсии в коде, называется итеративным процессом. Название запутывает: и рекурсивный и итеративный процесс — оба описывают рекурсию.
Помните наборы вызовов из предыдущего урока. Каждый новый созданный экземпляр, или ящик функции factorial ожидает от следующего экземпляра, что тот сделает возврат какого-нибудь значения. Никакого вычисления не производится, пока мы не спустимся до конца, к базовому случаю. Только тогда мы получим 1 и начнём выполнять умножения в обратном порядке: 1 умноженная на 2 — это 2, затем 3 умножается на два, получается 6.
С факториалом 3 никаких проблем, но представьте, что нужен факториал 100. Программе потребуется хранить в памяти множество чисел из-за откладывания всех операций умножения. Откладывание здесь — ключевое слово: суть рекурсивного процесса в откладывании вычислений до самого конца. Ничего не будет умножаться, пока процесс не спустится к базовому случаю, а если его остановить, программа ничего не будет знать и вы не получите никакой полезной информации, так как не дадите ей полностью закончить задачу. Рекурсивный процесс похож на человека, который выполняет работу за всю неделю в пятницу после обеда.
Вся эта информация о вычислениях называется состоянием. Всё, что ваша программа помнит в конкретный момент времени — это состояние: вычисления, константы, функции. И очень часто состояние — это причина самых разных проблем в программировании.
Оставлять все дела на пятничный полдень — не лучший способ работать. Способ получше — делать понемногу в понедельник, ещё немного во вторник и дальше в том же духе. Это итеративный процесс: когда работа распределяется равномерно на всю неделю.
Давайте запишем ту же функцию факториала используя итеративный процесс. Идея в том, чтобы не откладывать умножения, а умножить два числа сразу и передать результат в следующий шаг.
Как вы видите, всё выглядит уже не как математическая формула факториала. И это не похоже на функцию рекурсивного процесса из прошлого урока. Так обычно и бывает: код для рекурсивного процесса легче читать и понимать, поскольку он более близок к идее. Но он не достаточно эффективный. Итеративный процесс намного эффективнее, но он более усложнённый.
Функция факториала содержит в себе другую функцию. Помните, определения функций — это не сами ящики, а всего лишь их описания. Внутренняя функция iter принимает два аргумента: counter и accumulator. Counter отслеживает движение от n до 1. А accumulator — текущий результат умножения чисел от n до 1. Если counter достигает 1, accumulator возвращается — в этот момент он будет равен конечному ответу.
После того, как функция определена, у нас остаётся единственная строка в функции факториала: вернуть результат вызова функции iter с n и 1 в качестве аргументов.
Затем значение 6 просачивается в первый iter ящик, затем в ящик факториал, а затем возвращается в виде ответа.
Так выглядят вычисления шаг за шагом:
В любой момент программе необходимо помнить состояние, но его размер всегда неизменный — всего два числа.
Подобный итеративный процесс в целом может быть описан так:
И эта штука повторяется, пока не доберётся до терминального сценария.
Давайте повторим вкратце.
Теперь, после короткого тестового задания будет вероятно самое сложное упражнение этого курса. Но я уверен, что вы его раскусите. А когда вы это сделаете, вы почувствуете себя немного героем, как это было со мной.
Примечание
Очень важно понять отличия между рекурсией, рекурсивным процессом и итеративным процессом. Вот подробное объяснение в блоге Хекслета.
Дополнение к уроку
Выводы
Вызовем функцию из предыдущего урока:
Процесс вычисления, который создаёт эта функция, называется рекурсивным процессом. Основная его идея — откладывание вычисления до самого конца.
Вся информация о вычислениях, обо всём, что запоминает программа в любой конкретный момент (вычислениях, константах, функциях), называется состоянием. Множество проблем в программировании рождается из необходимости справиться с состоянием.
Суть итеративного процесса — вычисление с фиксированным количеством состояний.
Нам нужно с чего-то начать, потому что шаг 2 требует число из предыдущего шага, и мы начинаем с 1, потому что тогда n * 1 будет просто n:
Вот так выглядят вызовы iter, когда происходит вычисление 3!:
Итеративный процесс в целом:
Резюме
Дополнительные материалы
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты.
Нашли опечатку или неточность?
Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.
Что-то не получается или материал кажется сложным?
Загляните в раздел «Обсуждение»:
Об обучении на Хекслете
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
Наши выпускники работают в компаниях:
С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.