рекурсивная вложенность что такое
Допустим у нас есть такая структура вопросов и примечаний к ним, как указана на скриншоте справа, её мы и будем разбирать. Я не дизайнер, стилизировал как смог, чисто для этой статьи, так что извиняйте.
Пойдем по порядку.
Сначала объясню какие были условия.
Есть вопросы, внутри них могут быть примечания. При нажатии редактировать или сохранить — с сервера возвращается вёрстка вопроса/примечания и заменяется в шаблоне. Задача в том чтобы не потерять изменения примечаний при сохранении вопроса, если одновременно редактировались и вопрос и вложенное примечание.
Есть несколько вариантов решения этой проблемы, наверняка можно было отправлять всё разом на сервер а там уже разбирать, но это потребовало бы изменения структуры.
Мне понравился вариант с отложенным сохранением родительского вопроса, если имеются на сохранение некие дочерние элементы. Такое поведение бывает нужно в самых разных ситуациях, и даже в моей недолгой практике это потребовалось уже несколько раз.
Для нетерпеливых в самом конце статьи есть ссылки на демо.
Первый вопрос, никаких вложенностей.
Изменяем текст, нажимаем «save» — передаём id вопроса, измененный текст и получаем вёрстку в «обычном режиме» (на предпоследнем скриншоте).
Здесь всё легко, еще раз хочу акцентировать внимание на том, что после сохранения сервер возвращает нам вёрстку всего вопроса.
Второй вопрос, есть вложенности первого уровня.
Наверняка здесь есть много «WTF? моментов», поэтому распишу подробнее что я имел ввиду.
this всегда равен элементу save сохраняемого вопроса/примечания.
Просто мне так было удобнее ориентироваться в элементах.
С помощью деферреда.
Деферред работает таким образом, что если одновременно подписаться на несколько аякс запросов и один из них выполниться неудачно (вернёт error) — дальнейшая цепочка вызовов функций в деферред оборвется и все оставшиеся функции/запросы выполнены не будут. В аякс встроен свой деферред и поменять его поведение мы не можем, но, мы можем обернуть аякс запрос в некую обёртку и по завершении несмотря на успешность запроса — принудительно извещать об успешном выполнении.
$.Deferred можно создавать двумя способами…
… но если бы я сделал по первому способу, аякс пришлось бы вынести в отдельную функцию, а мне не хотелось, так что это чисто дело эстетики.
Третий вопрос, многоуровневая вложенность.
Казалось бы здесь код станет совсем страшным, но на самом деле прежняя реализация уже практически подходит для этого. Нужно добавить всего лишь одну функцию.
Дело в том, что..
… соберёт примечания на всех уровнях вложенности, и если родительское примечание сохраниться раньше дочернего, дочернее не успеет сохраниться. Проблема повторяется. Все что нам нужно сделать — заставить каждое родительское примечание вести себя как вопрос по отношению к дочерним элементам.
Т.е. если мы сохраняем примечание, и в beforeSend обнаруживается что внутри него есть еще не сохраненные примечание — приостанавливаем сохранение родительского примечания и ждем пока выполняться все дочерние.
При большом количестве вложенностей получается такая себе глубокая рекурсия.
p.s.1 Я во всех примерах рассматривал сохранение начиная с вопроса, но это только из-за того что вопрос находится в самом верху, так сказать самый трудный вариант. Конечно же, если в такой ситуации как изображена на последнем примере нажать сохранить на одном из примечаний, скажем 2м, все вложенные в него примечания также успешно сохраняться.
p.s.2 Во всех я примерах показал функцию saveData, которая вызывается при сохранении элемента. Также нужно добавить beforeSend функцию в ф-цию editData, которая вызывается при нажатии на редактирование элемента. Ведь если мы нажимаем редактировать вопрос, а внутри остались редактируемые примечания — их также нужно сохранить, но это вы уже можете посмотреть в демо.
Таким образом можно сохранять структуры любых вложенностей без потери редактируемых данных.
Для демонстрации пришлось применить немного php (для ответов с сервера), отчего продемонстрировать демо на jsFiddle не могу.
Я залил полностью работающий пример на Github, так что кому интересно можете скачать и поиграться у себя.
Также залил демо на один завалявшийся хостинг, посмотреть демо.
Я добавил задержку в 1 секунду чтобы можно было увидеть как происходит замена вёрстки. Каждый раз когда редактируется либо сохраняется вопрос/примечание, при замене вёрстки мигает фон текущего блока. Так легче понять что происходит.
Вот и всё, буду рад ответить на любые вопросы в комментариях.
Рекурсия, рекурсивный процесс и итеративный процесс
Рекурсия vs. какой-то процесс
Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.
пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину.
Теперь на секунду забудем про рекурсию, и просто подумаем про компьютеры. Для выполнения задач компьютерам нужны инструкции. Когда компьютер выполняет набор инструкций — это процесс. Ваш работающий сейчас браузер — это процесс. Простой цикл, выводящий на экран десять раз число «42» — это процесс. Некоторые задачи можно решать рекурсивно, то есть в инструкциях использовать эту концепцию, когда что-то является частью самого себя. В частности, функция может быть частью самой себя, то есть вызывать саму себя.
Есть два метода решения задач с использованием рекурсии: рекурсивный процесс и итеративный процесс. Рекурсия в них не отличается: в каждом из подходов функция вызывает саму себя, рекурсивно. Отличаются способы использования идеи рекурсии.
Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.
В чем отличие итеративного процесса от рекурсивного?
Главная фишка в аккумуляторе или, иными словами, в запоминании.
Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.
тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел
Рекурсивный процесс — это процесс с отложенным вычислением.
Итеративный процесс постоянно говорит «я сейчас посчитаю все что можно и продолжу» на каждом шаге рекурсии. Ему не нужно ничего запоминать вне вызова, он всегда считает все в первый возможный момент, и каждый шаг рекурсии может существовать в изоляции от прошлых, потому что вся информация передается из шага в шаг.
тут видно, что использование памяти не растет
Рекурсивный процесс это чувак, который все дела откладывает на вечер пятницы. В течение недели у него мало работы, а в пятницу завал. Но ему так нравится 🙂
Итеративный процесс это чувак, который все делает при первой возможности. У него работа равномерно распределена по неделе, а пятница — просто обычный день, но последний.
Tail call optimization
Отмотаем назад и рассмотрим во взаимосвязи два утверждения относительно рекурсивных функций, использующих итеративный процесс:
Читайте также: Язык программирования Ruby: особенности, перспективы, рынок труда
Хвостовая рекурсия (и её оптимизация) широко используется при написании программ на функциональных языках программирования.
Рекурсия для начинающих
В теме статьи обозначено «для начинающих», чтобы Гуру сильно не «пинали» за очевидные для них понятия. Тем не менее, объяснять рекурсию будем на основе понятий, которые ранее явно не часто были обозначены (блоки кода в теле рекурсивной функции).
Мы будем говорить о рекурсии в программировании. Не будем обсуждать, что такое рекурсия, и какая она бывает. На эту тему очень много статей и книг. Например, книга «Введение в рекурсивное программирование», автор Мануэль Рубио-Санчес, посвящена только рекурсии на 436 страницах.
Обычно есть вызывающая процедура и собственно рекурсивная функция. Собственно, теоретическая часть статьи заключается в изложении структуры рекурсивной функции. Изучать рекурсию проще используя процедуру с параметрами, а не функцию, возвращающую значение.
Для деревьев вместо условия применяется цикл. Деревья рассмотрим ниже.
Самая известная тема для рекурсии — это расчет факториала:
Очень красивый код, но не очень понятный …
Напишем код расчета факториала согласно нашей модели (Листинг 1):
Не так красиво, как (2), но мы учимся.
н – значение для вычисления факториала;
Ф – факториал (для н=4 будет 24).
Код достаточно понятный. Заметим только то, что Ф рассчитывается на прямом пути. На обратном пути (Возврат) – ничего не происходит. Полезно отследить изменение параметров в отладчике:
Здесь использованы блоки 1 и 2.
Блок1 – как правило на практике, нужен для подготовки Условия.
Блок2 – нужен для подготовки вызова рекурсивной процедуры (функции);
Теперь можно изменить процедуру Факториал убрать параметр к и приблизить её к каноническому виду (1).
На следующем шаге заменим процедуру на функцию и уберем вычисление Ф в Блоке2.
Для полного понимания предварительно рассмотрим следующий вариант:
Возвращаться будет 1.
Строки Останов = Истина добавлены для анализа переменных Ф и н в отладчике. Теперь нет параметра Ф в виде ссылки и возвращается локальное значение Ф, которое было зафиксировано при первом входе в рекурсию.
Исправим, добавим возврат переменной Ф. И увидим, что такое локальная переменная в рекурсивной функции – в отладчике. Это важно понимать.
На рисунке выше момент, когда вернулись в функцию, в которую входили с н = 2 и Ф = 12. Значение Ф сохранилось как для локальной переменной.
Это момент, когда еще не присвоено Ф возвращаемое значение функцией Факториал.
И вот на следующем шаге Ф переприсваивается.
В итоге функция отработает правильно.
Здесь мы не пишем функцию факториал, мы смотрим для чего нужны Блоки 1-5, как ведут себя переменные.
Рассмотрим простые примеры рекурсий в 1С.
Эта универсальная функция полезна для фиксации шапки отчета при программном выводе его:
Функция упрощена для примера. Настройки – настройки варианта макета, объявленные в Перем:
Рекурсивная функция написана в стиле листинга 1 и предельно понятна.
Основное применение рекурсии нашли при работе с деревьями. В 1С это в основном работа с иерархическими справочниками.
В теории деревьев различают корень, ветки и листья. Корень (ствол) это один элемент.
В 1С корня в классическом понимании у справочника нет. Корень — это сам иерархический справочник. Группы самого верхнего уровня имеют значение метода Уровень () = 0.
Рассмотрим пример определения самого старшего родителя для произвольного элемента справочника.
Каждый узел дерева имеет в точности одного родителя, за исключением корня, у которого нет родителей.
Это значит, что при движении по дереву вверх циклы не понадобятся.
Рассмотри пример использования рекурсий при обходе иерархического справочника с целью расчета себестоимости объектов строительства.
Есть объекты строительства. Объекты связаны иерархической моделью.
Нижние уровни дерева (листья) имеют прямые затраты. Их родители имеют косвенные затраты, которые нужно распределить на нижний уровень пропорционально прямым затратам объектов (листьев).
Прямые затраты – стоимость оборудования, косвенные – работы, необходимые для монтажа и ввода в эксплуатацию оборудования.
Вот пример из реальной БД:
Видим, что справочник «Объектов строительства» имеет до 7 уровней иерархии. В модели – есть объекты, которые будут приниматься к учету – основные средства. И есть работы, затраты которых нужно распределить:
Для решения задачи разберем алгоритм на следующей модели:
Рис. 1. Схема дерева
Рис.2. Дерево в справочнике объектов
Три уровня иерархии. Шесть объектов строительства с прямыми затратами и три с косвенными (группы).
Рассчитаем косвенные для объектов вручную.
База распределения для объекта Объект1 = 3000+2000 = 5000;
Косвенные от Объекта1:
для Объекта11 косвенные = 500 * 3000 / 5000 = 300.
для Объекта12 косвенные = 500 * 2000 / 5000 = 200.
База распределения для объекта Объект2 = 3000+2000+1000 = 6000;
Косвенные от Объекта2:
для Объекта21 косвенные = 600 * 3000 / 6000 = 300.
для Объекта22 косвенные = 600 * 2000 / 6000 = 200.
для Объекта23 косвенные = 600 * 1000 / 6000 = 100.
База распределения для объекта Объект0 – 5000+6000+1000 = 12000;
Для Объекта01 косвенные = 2400 * 1000 / 12000 = 200.
Для Объекта11 косвенные = 2400 * 3000 / 12000 = 600.
Для Объекта12 косвенные = 2400 * 2000 / 12000 = 400.
Для Объекта21 косвенные = 2400 * 3000 / 12000 = 600.
Для Объекта22 косвенные = 2400 * 2000 / 12000 = 400.
Для Объекта23 косвенные = 2400 * 1000 / 12000 = 200.
Для Объекта01 косвенные = 200
Для Объекта11 косвенные = 600 + 300 = 900
Для Объекта12 косвенные = 400 + 200 = 600
Для Объекта21 косвенные = 600 + 300 = 900
Для Объекта22 косвенные = 400 + 200 = 600
Для Объекта23 косвенные = 200 + 100 = 300
Итого косвенных 3500
Нужно сформировать запрос с Итогами, обязательно указать тип итогов «Элементы и иерархия».
В запросе должно быть так:
Мы выбираем дерево, потому что
В отладчике можно посмотреть данные.
Код более понятный – объект, строки, цикл.
Есть возможность реквизиты дерева использовать для алгоритма (записывать в реквизиты данные).
Объявляем переменную ОбъектыДляПриемки, которая будет видна во всех серверных функциях.
По кнопке с клиента вызываем серверную процедуру, в которой выполняем Запрос с итогами в иерархии. Выгружаем Результат Запроса в Дерево.
с типом обхода ПоГруппировкамСИерархией. Передаем в рекурсивную функцию Строки объекта строительства, который принимаем в эксплуатацию.
Принимаем в эксплуатацию в целом Объект0 (акты КС-11, КС-14), но к учету принимаем объекты самого нижнего уровня – основные средства (Дт01/Кт08.03) документом «Принятие к учету ОС».
Здесь важно – Объект0, это не корневой узел справочника! Но в дереве
он становится корневым (отбор по объекту).
Посмотрим данные дерева в отладчике:
Окно 1: Корень объекта строительства и его строки (Объект0)
Окно 2: Строка корня, нажимаем на ней F2
Окно 3: Строка корня раскрылась и видим Строки
Окно 4: После нажатия F2 на строке Строки
В четвертом окне 4 строки.
Проанализируем этот список (отмечен цифрой 4).
Первая строка – Объект01 – объект, который мы будем принимать к учету (это последний уровень, лист). Эта строка аналог записи в Выборке с типом – ДетальнаяЗапись.
Вторая строка – итоги по объекту Объект0. Эта строка аналог записи в Выборке с типом – ИтогПоИерархии.
Третья и четвертые строки – узлы дерева, их нужно раскрывать рекурсией.
Ниже приведены рекурсивные функции для расчета распределенных косвенных затрат.
В функции Рекурсия анализируем, какой тип строки дерева. Для детальной записи количество строк = 1 (своя строка). Для узла количество записей рано количеству потомков +1.
Запросом рассчитали суммарные значения прямых затрат для каждого узла дерева.
Во второй части условия проверяется ссылка Родителя, а если он не определён в первой части? Ответ: Если первая часть = Ложь то компилятор в условии И
не проверяет сведущие составляющие условия.
Поставим точку останова в функции КосвеныеОбъектовНаСервере как показано на рисунке ниже:
Увидим результаты запроса.
Так выглядит запись для корневой строки дерева после прохождения рекурсии. Сумма прямых затрат всех объектов нижних уровней равна 12 000.
На прямом пути для элемента самого нижнего уровня создаем строку в таблице значений:
Чтобы увидеть в отладчике ставим точку останове, показанную на рисунке ниже.
И сразу вызываем вторую рекурсивную функцию Косвенные.
Эта функция рассчитывает косвенные расходы для этого объекта от каждого родителя.
В итоге таблица ОбъектыДляПриемки будет выглядеть следующим образом:
Результат соответствует ручному расчету (Листинг 3).
Теперь в цикле для строк этой таблицы можно создавать документы «Принятие к учету ОС».
Но основная цель статьи рассмотреть использование различных областей рекурсивно функции. Перепишем ее следующим образом.
Добавим в таблицу ОбъектыДляПриемки колонку Прямые.
В результате расчета получим такую таблицу:
В этом варианте не используется вторая рекурсивная функция на прямом обходе дерева. Рассчитываем необходимые данные на обратном ходе. Конечно
Можно и нужно оптимизировать быстродействие этого решения, но цель здесь другая.
Выводы являются субъективным мнением автора.
При разработке алгоритмов с рекурсиями целесообразно использовать параметры функций, для возврата на верхние уровни значений, рассчитанных на нижних уровнях. Или использовать объявление переменных со сквозной видимостью в рекурсиях.
Алгоритмы в этом случае более «прозрачные».
Рассматривать целесообразность и использовать обратный ход рекурсивного расчета (область кода после выхода из рекурсивной функции).
Про смартфон — цены, обзоры и реальные отзывы покупателей
На сайте Pro-Smartfon найдёте отзывы и обзоры топовых смартфонов 2017 года. Всё о плюсах и минусах мобильных телефонов. Свежие фотографии, цены и реальные отзывы покупателей о лучших смартфонах
Рекурсивная вложенность компас как исправить
Возможные причины ограничения доступа:
Доступ ограничен по решению суда или по иным основаниям, установленным законодательством Российской Федерации.
Сетевой адрес, позволяющий идентифицировать сайт в сети «Интернет», включен в Единый Реестр доменных имен, указателей страниц сайтов сети «Интернет» и сетевых адресов, позволяющих идентифицировать сайты в сети «Интернет», содержащие информацию, распространение которой в Российской Федерации запрещено.
Сетевой адрес, позволяющий идентифицировать сайт в сети «Интернет», включен в Реестр доменных имен, указателей страниц сайтов в сети «Интернет» и сетевых адресов, позволяющих идентифицировать сайты в сети «Интернет», содержащие информацию, распространяемую с нарушением исключительных прав.
Рекурсия
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
У меня по работе, проектируя подстанции, когда делаю сборки сложные, в один прекрасный момент сборка не открывается. На пустом экране надпись «рекурсивная вложенность». Как с этим бороться не знаю. Заново леплю сборку. Вроде все то же самое сделаю и все открвывается. Причем, вот я ее закрыл, потом открываю — все ок. А на след. день прихожу и программа пишет «рекурсивная вложенность и не открывается файл. Я честно говоря не пойму, что это такое даже в бытовом плане — кроме как в примере — зеркало на против зеркала.
Обложили… демоны…
Вместо предисловия
Внезапно, как подводная лодка в степях Украины, спустя два года молчания, с новым перлом на связь выходит главный фронтенд-пират CSSSR Максон «Черная борода»!
Сейчас настало такое время, что в программирование, и в разработку интерфейсов в частности, стали приходить люди, не имеющие академического образования в области разработки ПО. Для малого и среднего бизнеса это, наверное, хорошо. Не нужно раскошеливаться на программистов, уже имеющих минимум 4 года работы за плечами. Но вот суровый энтерпрайз в этом отношении менее лоялен. Компиляция, интерпретация, AST, полиморфизм, SOLID, фасад, рекурсия — близкие выпускнику-программисту понятия, и в суровом энтерпрайзе он чувствует себя как минимум не одиноким.
Иная же ситуация с нами, реакт-программистами (да-да, и я тоже). Наступает момент, когда разработка интерфейсов требует не только вёрстки и создания «тупых» компонентов, но и знания фундаментальных инструментов программирования. И, к сожалению, такие метаморфозы часто не под силу стремящемуся из реакт-программистов в классические программисты. Литература, которая есть по фундаментальным основам программирования, безэмоциональна и беспощадна к новичкам. Для студентов-программистов ситуация иная, т.к. они варятся в этом «соку» несколько лет, и очередной бестселлер от дяди Боба или SICP не покажется им чем-то инопланетным.
Я попытаюсь без лишнего официоза, и при этом уделяя время деталям, познакомить всех причастных к проблеме «реакт-программистов» с одной из самых фундаментальных концепций программирования — рекурсией.
О значимости
Если суровый энтерпрайз — значит работа с данными. Если данные — то, скорее всего, в виде деревьев. Для работы с деревьями компьютерный бог не придумал ещё ничего лучше рекурсии. Но для начала нам нужно узнать врага в лицо, понять, как он работает изнутри. Ниже об этом.
Иди, вон, на кошках матрёшках тренируйся
Не переживайте — числа Фибоначчи, факториалы и прочие бояны — все будут рассмотрены. Матрёшка, а точнее процесс её изготовления идеально подходит для визуализации концепции рекурсии и процессов, происходящих внури неё. Напоминаю, что главной характеристикой матрёшки является количество матрёшек внутри — то есть вложенность, глубина матрёшки. Обозначим эту величину как n.
Как только работа закончена, матрёшку возвращают к предыдущему подмастерью, затем к предыдущему предыдущего и так до тех пор, пока не будут собраны все матрёшки.
Вот как может выглядеть этот процесс уже на JS:
Важно первым же делом проверить, а не базовый ли это случай? Не последняя ли матрёшка? Иначе рискуем рухнуть на питомник. Базовый случай всегда проверяется первым. Если нет, то строгаем матрёшки дальше.
Да, как можно заметить, подвызов всегда проще вызова. Т.е наш алгоритм идёт к уменьшению сложности до тех пор, пока вычисление уже не потребуется, т.к. уже нечего вычислять.
Декларативность
Нужно сказать пару слов о том, какая польза от рекурсии, если уже есть циклы. Уильям из Оккама недоволен.
В математике есть специальное обозначение для суммы нескольких чисел — Σ (сигма).
«Верни новый массив» — map()
«Преврати массив в Мегазорда» — reduce()
Напомню, что каждый из этих методов корнями уходит в ФП, где в основе всего лежит рекурсия. Всё иммутабельно, читабельно. Да и вообще стоит сказать, что есть языки программирования (Haskell вот), где вообще нет не только переменных, но и циклов. Только рекурсия, только хардкор!
— А что хочешь, то и пиши.
Как удачно выхваченная из контекста «Дневного дозора» фраза описывает рекурсию! «Что хочешь [получить], то и пиши». Рекурсия гораздо более юзерфрендли. Нам проще думать и рассуждать концепциями рекурсии. Декларативность рекурсии — важный, если не важнейший её плюс. Когда-нибудь нейросети смогут не только подражать Летову, но и писать код в суровом энтерпрайзе. Но пока с кодом работают люди, приоритетнее будет его читабельность и поддержка, а не скорость исполнения.
Ещё пара примеров, и двинемся дальше. Например, мы хотим найти сумму чисел в массиве:
Классика декларативного жанра: мы не пишем подробно, что именно нужно сделать с каждым элементом. Мы хотим результат в зависимости от условий. Что хочу получить, то и пишу.
Ну и высший уровень — это использовние более сильных абстракций над рекурсией:
Одна строка, ничего лишнего.
И ещё раз о деревьях, но уже подробнее. Собственно говоря, для деревьев пока не придумали ничего лучше рекурсии. Из полезного инструмента рекурсия превращается в жемчужину, когда мы имеем дело с деревьями.
Стандартный боян: нужно реализовать функцию, принимающую дерево и возвращающую массив листьев.
Мы хотим получить что-то такое:
И это ещё детский сад. На уровнях три и более начинается самый настоящий шабаш макарон и черных техник. И это мы только пытаемся получить массив листьев, ни о каких манипуляциях с полученным массивом не идёт и речи.
То же самое, но уже рекурсивно:
Вот и всё, и это решение работает для любых уровней вложенности.
Ещё раз обращу внимание: рекурсия — это не панацея и не серебрянная пуля от всех проблем. Существуют проблемы, которые гораздо проще решаются циклами. Более того, чаще всего рекурсивное решение менее производительно (об этом далее).
Без лишних слов, самый большой недостаток рекурсии: Uncaught RangeError: Maximum call stack size exceeded
Вот сейчас самое время заглянуть под капот и понять, почему же это происходит. Тут нам вновь стоит обратиться в столярную мастерскую.
Случаются заказы, когда, например, не было указано базовое условие или нам нужна матрёшка планковской длины, и тогда подмастерий набивается в мастерскую так много, что стены и перекрытия не выдерживают и мастерская падает на кошачий питомник.
К сожалению, в реальном мире ещё не придумали способ предотвратить такую кОтастрофу, кроме как уволить всех подмастерий и не делать матрёшек вообще. Во фронтенде немного иначе: RangeError — это защита JS-движка от падения нашей программы. Как только движок видит, что стек начинает странно расти, выполнение программы прерывается. Движок выбрасывает эту ошибку, предотвращая переполнение памяти.
Разбираться в этом нужно с понимания того, что такое стек вызова. Это среда, в которой выполняются функции. Каждый вызов функции влечёт за собой выделение фрагмента (фрейма) памяти. Фрейм содержит определённую информацию о текущем состоянии выполнения функции, включая значения любых переменных. Причина, по которой эта информация должна храниться во фрейме, состоит в том, что функция может вызывать другую функцию, которая приостанавливает текущую функцию. Когда другая функция заканчивается, движку необходимо восстановить точное состояние с момента его приостановки.
Давайте визуализируем этот процесс в общем (без циклов/рекурсий) случае.
Диаграммы такого вида украдены мною отсюда.
Когда функция закачивает свою работу, её фрейм удаляется, выпадает из стека.
Вот, кажется, вся теория по стеку, которая нам нужна. Теперь посмотрим, как ведет себя стек при работе с циклами и рекурсиями.
Есть функция, возвращающая нам массив чисел, находящийся между заданными точками:
Ничего удивительного, алгоритм работает просто и эффективно расходует память (создался только один фрейм).
Иная ситуация будет, если мы перепишем функцию в рекурсивный вид:
Стек начинает расти. Ну и что? Чтобы это стало проблемой, мы должны получить тысячи вызовов в контексте. В современных реалиях такая ситуация практически невозможна. Но только не в случае с рекурсией.
В общем-то ещё не произошло ничего страшного, но движок, анализируя лавинообразный рост стека понимает, что что-то пошло не так, и останавливает выполнение программы.
Пора озвучить главный недостаток рекурсии: расход памяти. Далее будут описаны способы избежать роста стека и гибели кошек заодно.
Хвостовые вызовы
Надо сказать, что сама идея хвостовых вызовов не нова и напрямую не связана ни с рекурсией, ни с JS. Еще в 1960-х годах, когда компьютеры были великанами, было сделано важное наблюдение — если любой вызов является последней операцией перед возвратом из функции, то стек нам не нужен. Если рекурсивный вызов является последней операцией перед выходом из вызывающей функции, и результатом вызывающей функции должен стать результат, который вернёт рекурсивный вызов, то сохранение контекста уже не имеет значения — ни параметры, ни локальные переменные использоваться уже не будут, а адрес возврата уже находится в стеке. Ещё раз: если вызов bar из baz происходит в самом конце выполнения baz (иначе говоря «в хвосте»), то стек вызовов для baz не нужен вовсе.
Хвостовой вызов выглядит так, и никак иначе (чистый хвостовой вызов aka Proper Tail Call aka PTC):
… не хвостовые вызовы.
Приведение кода к хвостовому вызову называется оптимизацией хвостового вызова (далее по тексту TCO — Tail Call Optimization). TCO по умолчанию есть во многих языках, активно использующих рекурсию — например в Haskell. Там компилятор, видя вызов в «хвосте» (tail call position), применяет оптимизацию, приводя рекурсию к циклу.
Непременно нужно отметить, что TCO-версия получена с помощью Babel и лишь отчасти отражает действительный результат оптимизации компилятором. Но суть передана на 100% верно: рекурсия будет превращена в цикл. Реальный результат в виде ассемблерного кода слишком низкоуровневый, чтобы человек смог его осилить.
Получается, что ТCO в случае рекурсии решает главную проблему — потребление памяти. Это не значит, что программа будет работать быстрее, зачастую хвостовые вызовы работают медленее обычных. И в этом плане TCO не является оптимизацией в её привычном понимании — оптимизацией скорости работы. Но TCO позволяет нам использовать рекурсию там, где это необходимо, не беспокоясь о переполнении стека. А это важнее скорости, ибо, как уже писалось, рекурсия гораздо более декларативна: Что хочу получить, то и пишу.
Ну и конечно же, в мире фронтенда TCO не было до ES6) Вспоминается старик Крокфорд:
Any sufficiently interesting JavaScript library contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell.
«Любая достаточно интересная библиотека JavaScript содержит забагованную, плохо документированную, медленную реализацию половины Haskell».
Тут, в общем-то, впору заканчивать статью: используйте Elm во фронтенде и не парьтесь насчет TCO, иммутабельности и типизации — всё идёт из коробки.
С вами был фронтенд-пират из CSSSR! Читайте наш блог и берегите себя!