Итеративный процесс — Основы программирования

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

https://goo.gl/3ggX0S

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tail call optimization

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

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

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

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

---

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

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

Об обучении на Хекслете

• Статья «Как учиться и справляться с негативными мыслями»
• Статья «Ловушки обучения»
• Статья «Сложные простые задачи по программированию»
• Урок «Как эффективно учиться на Хекслете»
• Вебинар «Как самостоятельно учиться»