Рекурсивная вложенность компас как исправить

Возможные причины ограничения доступа:

Доступ ограничен по решению суда или по иным основаниям, установленным законодательством Российской Федерации.

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

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

Рекурсия
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

У меня по работе, проектируя подстанции, когда делаю сборки сложные, в один прекрасный момент сборка не открывается. На пустом экране надпись «рекурсивная вложенность». Как с этим бороться не знаю. Заново леплю сборку. Вроде все то же самое сделаю и все открвывается. Причем, вот я ее закрыл, потом открываю — все ок. А на след. день прихожу и программа пишет «рекурсивная вложенность и не открывается файл. Я честно говоря не пойму, что это такое даже в бытовом плане — кроме как в примере — зеркало на против зеркала.
Обложили… демоны…

Вместо предисловия

Внезапно, как подводная лодка в степях Украины, спустя два года молчания, с новым перлом на связь выходит главный фронтенд-пират CSSSR Максон «Черная борода»!

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

Иная же ситуация с нами, реакт-программистами (да-да, и я тоже). Наступает момент, когда разработка интерфейсов требует не только вёрстки и создания «тупых» компонентов, но и знания фундаментальных инструментов программирования. И, к сожалению, такие метаморфозы часто не под силу стремящемуся из реакт-программистов в классические программисты. Литература, которая есть по фундаментальным основам программирования, безэмоциональна и беспощадна к новичкам. Для студентов-программистов ситуация иная, т.к. они варятся в этом «соку» несколько лет, и очередной бестселлер от дяди Боба или SICP не покажется им чем-то инопланетным.

Я попытаюсь без лишнего официоза, и при этом уделяя время деталям, познакомить всех причастных к проблеме «реакт-программистов» с одной из самых фундаментальных концепций программирования — рекурсией.

О значимости

Если суровый энтерпрайз — значит работа с данными. Если данные — то, скорее всего, в виде деревьев. Для работы с деревьями компьютерный бог не придумал ещё ничего лучше рекурсии. Но для начала нам нужно узнать врага в лицо, понять, как он работает изнутри. Ниже об этом.

Иди, вон, на кошках матрёшках тренируйся

Не переживайте — числа Фибоначчи, факториалы и прочие бояны — все будут рассмотрены. Матрёшка, а точнее процесс её изготовления идеально подходит для визуализации концепции рекурсии и процессов, происходящих внури неё. Напоминаю, что главной характеристикой матрёшки является количество матрёшек внутри — то есть вложенность, глубина матрёшки. Обозначим эту величину как n.

Представим себе двухэтажное здание со столярной мастерской на втором этаже. В мастерскую прилетает заказ на изготовление матрёшки c n = 5 . Что происходит далее: мастер берёт и делает первую, самую большую матрёшку. Но работа ещё не окончена, так как матрёшка внутри пустая. Далее мастер вызывает своего подмастерье и ставит ему задачу сделать матрёшку, но уже со вложенностью 4, т.е n — 1 . Какие аналогии мы уже можем привести из реального программирования? вызывает своего подмастерье и ставит ему задачу сделать матрёшку — по сути это вызов подфункции, или по-другому: рекурсивный вызов функции. Подмастерье делает матрёшку со вложенностью 4 и также делегирует остальную работу по созданию матрёшки меньшей вложенности другому подмастерью. И так далее происходит передача работы, пока не будет озадачен последний подмастерье, который сделает последнюю, шестую матрёшку. Достигнута ситуация, когда не трубуется создавать новых, ещё меньших матрёшек, поэтому последняя матрёшка делается неделимой.

Читайте также  Пульт для телевизора мистери на андроид

Как только работа закончена, матрёшку возвращают к предыдущему подмастерью, затем к предыдущему предыдущего и так до тех пор, пока не будут собраны все матрёшки.

Что тут важно подчеркнуть? На матрёшках мы изобразили два главных требования к рекурсии. А именно: рекуррентный и базовый случай. Рекуррентный случай — это то, что вообще должна делать рекурсивная функция, это её описание. Конкретно в нашем примере: создание матрёшки со вложенностью n – 1 . Если рекуррентный случай не описан, то возникнет ситуация, при которой обращение идёт не к подмастерью, а к мастеру. Мастер вызывает мастера, мастер вызывает мастера, мастер вызывает мастера — ничего не происходит, наш алгоритм не работает, проект «матрёшка» стоит на месте.

Базовый случай – это то, к чему должна стремиться рекурсия. По его достижению прекращается выполнение работы или вычисления, и полученный результат возвращается обратно. Если мы не укажем базовый случай, то возникнет такая ситуация, когда подмастерья будут приходить и приходить, и в конце концов мастерская рухнет со второго этажа прямо на кошачий питомник. В реальной жизни мы получим «падение программы» и Uncaught RangeError: Maximum call stack size exceeded , об этой ошибке мы ещё поговорим позже.

Вот как может выглядеть этот процесс уже на JS:

Важно первым же делом проверить, а не базовый ли это случай? Не последняя ли матрёшка? Иначе рискуем рухнуть на питомник. Базовый случай всегда проверяется первым. Если нет, то строгаем матрёшки дальше.

Да, как можно заметить, подвызов всегда проще вызова. Т.е наш алгоритм идёт к уменьшению сложности до тех пор, пока вычисление уже не потребуется, т.к. уже нечего вычислять.

Декларативность

Нужно сказать пару слов о том, какая польза от рекурсии, если уже есть циклы. Уильям из Оккама недоволен.

В математике есть специальное обозначение для суммы нескольких чисел — Σ (сигма).

Σ9 гораздо проще для восприятия, компактнее и читабельнее, чем 1+2+3+4+5+6+7+8+9 . Так вот, рекурсия — это сигма в мире программирования. Нам важен результат действия, но нам необязательно смотреть под капот и видеть потроха действия. Нам не нужно проходить руками по массиву, объявлять переменную, что-то делать и потом сохранять этот результат. Говоря на языке JS, мы можем сказать, например:

«Верни новый массив» — map()

«Преврати массив в Мегазорда» — reduce()

Напомню, что каждый из этих методов корнями уходит в ФП, где в основе всего лежит рекурсия. Всё иммутабельно, читабельно. Да и вообще стоит сказать, что есть языки программирования (Haskell вот), где вообще нет не только переменных, но и циклов. Только рекурсия, только хардкор!

— А что хочешь, то и пиши.

Как удачно выхваченная из контекста «Дневного дозора» фраза описывает рекурсию! «Что хочешь [получить], то и пиши». Рекурсия гораздо более юзерфрендли. Нам проще думать и рассуждать концепциями рекурсии. Декларативность рекурсии — важный, если не важнейший её плюс. Когда-нибудь нейросети смогут не только подражать Летову, но и писать код в суровом энтерпрайзе. Но пока с кодом работают люди, приоритетнее будет его читабельность и поддержка, а не скорость исполнения.

Читайте также  Почему не добавляешь в друзья

Ещё пара примеров, и двинемся дальше. Например, мы хотим найти сумму чисел в массиве:

Классика декларативного жанра: мы не пишем подробно, что именно нужно сделать с каждым элементом. Мы хотим результат в зависимости от условий. Что хочу получить, то и пишу.

Ну и высший уровень — это использовние более сильных абстракций над рекурсией:

Примечание: самостоятельно писать ни map, ни filter, ни reduce не нужно. В JavaScript всё уже идёт из коробки. И как можно заметить на примере reduce , эти абстракции построены на рекурсии. Так они работают в функциональных языках, где рекурсия — основной инструмент вычислений.

Одна строка, ничего лишнего.

И ещё раз о деревьях, но уже подробнее. Собственно говоря, для деревьев пока не придумали ничего лучше рекурсии. Из полезного инструмента рекурсия превращается в жемчужину, когда мы имеем дело с деревьями.

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

Мы хотим получить что-то такое:

И это ещё детский сад. На уровнях три и более начинается самый настоящий шабаш макарон и черных техник. И это мы только пытаемся получить массив листьев, ни о каких манипуляциях с полученным массивом не идёт и речи.

То же самое, но уже рекурсивно:

Вот и всё, и это решение работает для любых уровней вложенности.

Ещё раз обращу внимание: рекурсия — это не панацея и не серебрянная пуля от всех проблем. Существуют проблемы, которые гораздо проще решаются циклами. Более того, чаще всего рекурсивное решение менее производительно (об этом далее).

Без лишних слов, самый большой недостаток рекурсии: Uncaught RangeError: Maximum call stack size exceeded

Вот сейчас самое время заглянуть под капот и понять, почему же это происходит. Тут нам вновь стоит обратиться в столярную мастерскую.

Случаются заказы, когда, например, не было указано базовое условие или нам нужна матрёшка планковской длины, и тогда подмастерий набивается в мастерскую так много, что стены и перекрытия не выдерживают и мастерская падает на кошачий питомник.

К сожалению, в реальном мире ещё не придумали способ предотвратить такую кОтастрофу, кроме как уволить всех подмастерий и не делать матрёшек вообще. Во фронтенде немного иначе: RangeError — это защита JS-движка от падения нашей программы. Как только движок видит, что стек начинает странно расти, выполнение программы прерывается. Движок выбрасывает эту ошибку, предотвращая переполнение памяти.

Разбираться в этом нужно с понимания того, что такое стек вызова. Это среда, в которой выполняются функции. Каждый вызов функции влечёт за собой выделение фрагмента (фрейма) памяти. Фрейм содержит определённую информацию о текущем состоянии выполнения функции, включая значения любых переменных. Причина, по которой эта информация должна храниться во фрейме, состоит в том, что функция может вызывать другую функцию, которая приостанавливает текущую функцию. Когда другая функция заканчивается, движку необходимо восстановить точное состояние с момента его приостановки.

Давайте визуализируем этот процесс в общем (без циклов/рекурсий) случае.

Диаграммы такого вида украдены мною отсюда.

Тут GC — это глобальный контекст выполнения, тот, в котором работает интерпретатор JS. Стрелкой указан фрейм памяти, который выделяется под нужды программы. Наш код имеет две функции — foo и bar , существование которых повлекло создание двух таких фреймов памяти. Если бы bar() вызывал внутри себя ещё одну функцию, то сверху оказался бы ещё один фрейм. И так далее.

Когда функция закачивает свою работу, её фрейм удаляется, выпадает из стека.

Читайте также  Программа мордочки на лицо

Вот, кажется, вся теория по стеку, которая нам нужна. Теперь посмотрим, как ведет себя стек при работе с циклами и рекурсиями.

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

Вызвав range(1,3); , мы получим такую диаграмму:

Ничего удивительного, алгоритм работает просто и эффективно расходует память (создался только один фрейм).

Иная ситуация будет, если мы перепишем функцию в рекурсивный вид:

Стек начинает расти. Ну и что? Чтобы это стало проблемой, мы должны получить тысячи вызовов в контексте. В современных реалиях такая ситуация практически невозможна. Но только не в случае с рекурсией.

В общем-то ещё не произошло ничего страшного, но движок, анализируя лавинообразный рост стека понимает, что что-то пошло не так, и останавливает выполнение программы.

Вспоминаете? . подмастерий набивается в мастерскую так много, что стены и перекрытия не выдерживают и мастерская падает на кошачий питомник.

Пора озвучить главный недостаток рекурсии: расход памяти. Далее будут описаны способы избежать роста стека и гибели кошек заодно.

Хвостовые вызовы

Надо сказать, что сама идея хвостовых вызовов не нова и напрямую не связана ни с рекурсией, ни с 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! Читайте наш блог и берегите себя!

Ссылка на основную публикацию
Adblock detector