Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос нашим менторам. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Итеративный процесс

Видео может быть заблокировано из-за расширений браузера. В статье вы найдете решение этой проблемы.

Визуализация итеративного процесса

https://goo.gl/3ggX0S

Копия сообщения из сообщества:

Рекурсия vs. какой-то процесс

Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.

пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину...

пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину...

Теперь на секунду забудем про рекурсию, и просто подумаем про компьютеры. Для выполнения задач компьютерам нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — это процесс. Простой цикл, выводящий на экран десять раз число "42" — это процесс. Некоторые задачи можно решать рекурсивно, то есть в инструкциях использовать эту концепцию, когда что-то является частью самого себя. В частности, функция может быть частью самой себя, то есть вызывать саму себя.

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

Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.

В чем отличие итеративного процесса от рекурсивного?

Главная фишка в аккумуляторе или, иными словами, в запоминании.

Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.

  • Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя.
  • Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.

Рекурсивный процесс

тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел

Рекурсивный процесс — это процесс с отложенным вычислением.

Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг.

  • Когда итеративный процесс считает факториал 6, то ему не нужно запоминать числа. Нужно лишь считать и передавать результат дальше, в новый вызов.
  • Когда мы находимся в очередном вызове функции, снаружи этого вызова в памяти ничего не нужно запоминать.

Итеративный процесс

тут видно, что использования памяти не растет


Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится :)

Итеративный процесс это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница — просто обычный день, но последний.


Tail call optimization

Отмотаем назад и рассмотрим во взаимосвязи два утверждения относительно рекурсивных функций, использующих итеративный процесс:

  • Во-первых, такие функции являются рекурсивными. Это значит, что для каждого (очередного) рекурсивного вызова в стек вызовов записывается вся информация, связанная с этим конкретным вызовом (параметры функции и её локальные переменные, адрес возврата в точку вызова). Т.е. выделяется дополнительная область памяти (лексический контекст функции, область видимости), обслуживающая данный рекурсивный вызов, а так как это стек вызовов, то контексты предыдущих рекурсивных вызовов также продолжают занимать память. Достижение большой глубины рекурсии (или же если она вовсе является бесконечной, т.е. не достигается терминальное условие выхода из рекурсии) приводит к переполнению стека (ведь он ограничен в размерах) и аварийному завершению всей программы.
  • Во-вторых, в контексте каждого очередного рекурсивного вызова такой функции хранится вся необходимая информация для его успешного выполнения. Он самодостаточен и никак не зависит от предыдущих контекстов (помните, "этот чувак ничего не откладывает на потом, на вечер пятницы..."?!). В наших практиках на Хекслете мы реализовывали такое поведение благодаря использованию аккумулятора acc, передающегося в качестве аргумента из одного вызова в другой и накапливающего в себе результат вычисления необходимого значения. Получается, что, грубо говоря, на каком бы по уровню вложенности рекурсивном вызове мы не находились, все предыдущие уже не имеют значения и являются "бесполезной обузой", нагружающей память. В т.ч. это распространяется и на самый последний рекурсивный вызов (где срабатывает терминальное условие), который сразу готов вернуть готовое вычисленное значение из функции, ему не нужны для этого предыдущие контексты в стеке.

Отсюда напрашивается вопрос, как использовать рассмотренные преимущества итеративного процесса и одновременно избавиться от недостатка рекурсивных функций, т.е. от неумолимого роста использования памяти. И сразу же нарисовывается ответ - избавить процесс от заполнения стека "ненужными" контекстами предыдущих вызовов и обеспечить прямой возврат из функции при достижении терминального условия. Для этого служит так называемая Tail call optimization, или оптимизация хвостовой рекурсии (рассмотренный выше итеративный процесс как раз можно отнести к хвостовой рекурсии). Благодаря оптимизации состояния стека, она придаёт итеративному процессу вид "плоской" итерации (см. картинку выше), исключается его переполнение из-за большой глубины рекурсии.

Хвостовая рекурсия (и её оптимизация) широко используется при написании программ на функциональных языках программирования.


<span class="translation_missing" title="translation missing: ru.web.courses.lessons.mentors.mentor_avatars">Mentor Avatars</span>

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят менторы из команды Хекслета или другие студенты.

Зарегистрироваться

или войти в аккаунт

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг». Защита от спама reCAPTCHA «Конфиденциальность» и «Условия использования».