Что такое глубина рекурсии
Перейти к содержимому

Что такое глубина рекурсии

  • автор:

Что такое глубина рекурсии

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2024. Stepik

Наши условия использования и конфиденциальности

Get it on Google Play

Public user contributions licensed under cc-wiki license with attribution required

Рекурсия

Рекурсия (recursion) — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга.

Известная шутка гласит: «Чтобы понять рекурсию, надо понять рекурсию».

«IT-специалист с нуля» наш лучший курс для старта в IT

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

Это работает так: функция A от единицы запускает функцию A от двойки, та — от тройки, и так далее, пока не будет высчитано нужное значение. Чтобы рекурсивный вызов закончился, нужно сразу прописать в функции A условие выхода из рекурсии: например, если получено какое-то значение, нужно не запускать функцию заново, а вернуть некоторый результат.

Если не прописать условие выхода, рекурсия будет бесконечной. А пока условие выхода не достигнуто, все вызванные экземпляры функции A будут работать одновременно — один вкладывает другой в себя.

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

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

vsrat_7 1 (1)

Кто пользуется рекурсией и зачем она нужна

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

Обычно рекурсию применяют при расчетах, которые подразумевают использование результата одного шага для подсчитывания другого. Например, расчет фрактала и его рисование. Зачастую подобные задачи можно решить и без рекурсии, но ее использование делает код проще, короче и быстрее, чем альтернативные варианты. Правда, рекурсия может слишком нагружать компьютер, поэтому такие решения применяют не всегда.

Рекурсию можно встретить и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Например, фрактальные формы вроде листа папоротника или снежинки — рекурсивные. Вложенные предложения — тоже. А самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.

Программисты пользуются рекурсией и ради забавы. Например, известная аббревиатура GNU расшифровывается как GNU is Not Unix – первая буква скрывает под собой ту же аббревиатуру. Это тоже рекурсия.

Отличия рекурсии от цикла

На интуитивном уровне рекурсивный вызов легко перепутать с циклом. И то, и другое понятие подразумевает, что функция выполняется несколько раз. Но есть принципиальное различие:

  • в цикле новые функции не вызываются внутри вызванных ранее;
  • рекурсия же — это функция, вызывающая сама себя с другими аргументами.

Простыми словами: инструкция с пунктом «Вернись к пункту 1» — это цикл, инструкция с пунктом «Прочитай инструкцию заново» — рекурсия.

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

Прерывание рекурсии

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

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

Например, если n > 1, то вызвать A(n-1). Иначе вернуть 1. Получается, что когда n станет меньше или равен единице, то A не запустится заново — очередной экземпляр просто вернет единицу. Остальные экземпляры получат нужный себе результат и тоже закроются по каскаду. Этот процесс называется обратным ходом рекурсии. А то, что было до него, — прямым ходом.

Количество открытых в итоге функций называется глубиной рекурсии.

Пример рекурсии: расчет чисел Фибоначчи

Известный пример рекурсивных расчетов — числа Фибоначчи. Каждое следующее число в ряду — сумма двух предыдущих, начиная с 1.

Получается так: 1, 1, 2, 3, 5, 8, 13, 21 и так далее. Использование рекурсии здесь — напрашивающийся и интуитивно понятный способ расчета:

  • допустим, функция называется fibonacci(n) и рассчитывает n-е по счету число Фибоначчи;
  • на первом шаге функция вызывает fibonacci(n-1) и fibonacci(n-2), то есть себя, но с другими аргументами, и складывает получившиеся результаты;
  • новые вызовы будут делать то же самое, пока n не дойдет до единицы или нуля — это первое число Фибоначчи, и в таком случае функция вернет 1;
  • предыдущий экземпляр функции получит два результата 1 — от единицы и нуля, сложит их и отправит «назад» к более ранним соседям;
  • в итоге все вызванные функции получат от своих «потомков» ответ, сложат полученные значения и вернут их самой первой функции fibonacci(n);
  • та сложит финальные значения, вернет результат и закроется.

Это только один простой пример; рекурсивных алгоритмов намного больше. Еще один известный — расчет факториала числа.

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Другие примеры рекурсивных расчетов

  • Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
  • Расчет и изображение фракталов — конструкций, где более мелкие элементы повторяют более крупные. Яркие примеры фракталов — снежинка и лист папоротника.
  • Обход ветвящихся структур данных, например графов и деревьев.
  • Компьютерный анализ естественного языка, фраз и предложений.
  • Поиск пути в лабиринте и построение маршрутов — к примеру, алгоритмы DFS и BFS.
  • Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
  • Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
  • Операции с системами счисления, к примеру перевод чисел из одной в другую.

За пределами математики и информатики можно вспомнить много других примеров рекурсии: от самовозбуждения электронных схем до сказок «Тысячи и одной ночи».

Прямая и косвенная рекурсия

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

  • Прямая вызывает сама себя напрямую. То есть функция A вызывает функцию A с другими аргументами.
  • Косвенная действует через «третью» функцию. Функция A вызывает функцию B, а та в свою очередь снова вызывает функцию A. Это тоже рекурсия, просто менее очевидная.

Еще бывают линейная и каскадная рекурсии. В линейной экземпляр функции вызывает сам себя только один раз, в каскадной — несколько. Например, расчет чисел Фибоначчи — каскадная рекурсия, потому что функция вызывает себя дважды: для n-1 и n-2.

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

Одну и ту же рекурсию можно использовать по-разному. Например, есть понятия рекурсивного и итеративного процесса. И там, и там применяется рекурсия, но различается подход к ней.

В рекурсивном процессе все расчеты откладываются «на потом», как в примере с числами Фибоначчи. Конечный расчет делает тот экземпляр функции, который вызвали в последнюю очередь, а потом результаты по каскаду передаются предыдущим.

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

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

Преимущества рекурсии

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

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

Наглядность. Некоторые задачи, вроде тех же чисел Фибоначчи или факториалов, — рекурсивные по самому своему определению. То же самое касается задач на ряды, фракталы и так далее. Решить такую задачу через рекурсию — один из наиболее наглядных и интуитивно понятных способов. Более того: люди пользуются рекурсией все время, даже просто когда разговаривают, и это лишний раз работает на интуитивное ее понимание.

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

Красота. Наконец, сам концепт многие считают красивым и изящным. Это и правда так — посмотрите на фракталы и снежинки: в них есть определенная красота. Рекурсию используют даже в искусстве: от матрешек до сложных узоров, украшающих готические соборы.

Недостатки рекурсии

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

Риск переполнения. При всем перечисленном программисты пользуются рекурсией довольно осторожно. Она устроена так, что, пока не выполнится последний вызов функции, все предыдущие не завершатся — ведь они как бы «вкладывают» в себя последующие. Поэтому такие программы отнимают много ресурсов компьютера. Так что разработчики смотрят и на параметр производительности и решают, что выгоднее в конкретном случае — использовать рекурсию или нет.

Риск бесконечности. Если что-то пошло не так и программист случайно получил бесконечную рекурсию, единственный выход — принудительно закрыть программу. А потом переписать ее, чтобы ошибка не повторялась при следующем запуске.

Чем пользоваться: рекурсией или циклом

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

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

Понимание, что лучше использовать в конкретном случае, приходит с опытом. Начинающим разработчикам в любом случае стоит освоить рекурсию: это важная часть программирования и информатики вообще.

Как начать работать с рекурсией

Концепт и примеры рекурсивных функций можно найти в любом учебнике по программированию. Обычно начинающим предлагают потренироваться на простых «классических» задачах вроде чисел Фибоначчи или расчета факториала. Затем можно переходить к более сложным заданиям: обход графа, анализ текста или что-либо еще. А какой язык выбрать — зависит от ваших предпочтений и пожеланий к отрасли.

Если вы хотите познакомиться с большим количеством концептов из информатики — записывайтесь на курсы! Вы узнаете, как работают разные процессы, и сделаете первые шаги к новой востребованной профессии.

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать

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

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

— Как она сложена?
— Превосходно! Только рука немного торчит из чемодана.

Именно пытаясь разместить стройную теорию алгоритма в жесткий рюкзак реальных ресурсов и приходится постоянно кроить по живому, перепаковывать, и вместо красивых и стройных определений Фибоначчи:

 def fib(n): if n=0") if n>1: return fib(n-1) + fib(n-2) return n 

приходится городить всевозможные грязные хаки, начиная от:

 @memoized def fib(n): if n=0") if n>1: return fib(n-1) + fib(n-2) return n 

И заканчивая вообще:

 def fib(n): if n=0") n0 = 0 n1 = 1 for k in range(n): n0, n1 = n1, n0+n1 return n0 

Так что же такое рекурсия?

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

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

Теперь давайте рассмотрим классический пример: обход дерева в глубину. Впрочем нет, давайте рассмотрим другой пример: нам надо распечатать дерево выражений в форме обратной польской записи. То есть для дерева 1 мы хотим напечатать «2 2 +» а для дерева 2 «2 2 + 2 2 + *».

\begin \node (is-root) child < node > child < node >; \path (is-root) +(0,+0.5\tikzleveldistance) node >; \end \begin \node (is-root) child < node [sibling distance=1cm] child  child  > child < node [sibling distance=1cm] child  child  >; \path (is-root) +(0,+0.5\tikzleveldistance) node >; \end

Как легко видеть, задача превращается в простой «обход дерева в глубину»: для каждого узла выводим содержимое всех его дочерних элементов, после чего выводим сам узел. То есть код будет:

class TreeNode(object): def __init__(self, value=None, children=[]): self.value = value self.children = children def printTree(node): for child in node.children: printTree(child) print node.value, def main(): tree1 = TreeNode("+", [ TreeNode(2), TreeNode(2) ]) tree2 = TreeNode("*", [ TreeNode("+", [ TreeNode(2), TreeNode(2) ]), TreeNode("+", [ TreeNode(2), TreeNode(2) ]) ]) print "Tree1:", printTree(tree1) print print "Tree2:", printTree(tree2) print if __name__ == "__main__": main() 

Казалось бы, всё отлично! Код прекрасно работает до тех пор, пока дерево соответствует требованиям: любой узел имеет массив детей (возможно пустой) и какое-либо значение. Кто скажет какое еще требование к этому дереву?

Не буду томить. Требование: не сильно большая глубина дерева. Как так? А вот как:

def buildTree(depth): root = TreeNode("1") node = root for k in range(depth): node = TreeNode("--", [ node ]) return node def depthTest(depth): tree = buildTree(depth) print "Tree of depth", depth, ":", printTree(tree) def main(): for d in range(10000): depthTest(d) 

Запускаем, и ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Лезем в документацию, и обнаруживаем функцию sys.getrecursionlimit. А теперь давайте отойдём от мира интерпретируемых языков, и перейдём в мир языков, которые запускаются прямо на процессоре. Например, на C++.

Мысленно перепишем 1-в-1 этот код на С++ (оставлю эту задачу читателю в качестве разминки), и попробуем найти предел, когда приложение упрется в ограничение…

для ленивых

#include #include #include using namespace std; class TreeNode < public: string value_; vectorchildren_; TreeNode(const string& value, const vector& children): value_(value), children_(children) <> virtual ~TreeNode() <> >; void printTree(const TreeNode* node) < for(auto i : node->children_) printTree(i); cout value_ TreeNode* buildTree(const int depth) < auto root = new TreeNode("1", <>); auto node = root; for(int i = 0; i  return node; > void depthTest(const int depth) < auto tree = buildTree(depth); cout int main() < for(int d=60000;; d+=16384) < depthTest(d); >> 

Запускаем… «Bus error (core dumped)». Судя по gdb, в момент падения стек глубиной 104790 фреймов. А что произойдёт, если мы захотим печатать не просто подряд через пробелы, а выводить еще «» вокруг выражений? Ну то есть для дерева 1 чтобы результатом было а для дерева 2 — <*>? Перепишем…

def printTree(node): opened = False for child in node.children: if not opened: print "", 

Ничего не изменилось, по прежнему падает при попытке распечатать дерево глубиной 997. А теперь то же самое, но на плюсах… Опа. Глубина стека при падении — 87327. Стоп. Мы всего-то добавили одну локальную переменную, никак не влияющую на алгоритм и суть происходящего, а предельный размер дерева сократился на 17%! А теперь самое весёлое — всё это сильно зависит от опций компилятора, от того, на какой платформе выполняется, в какой ОС и с какими настройками.

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

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

Так в чем же проблема?

Использование рекурсивного алгоритма подразумевает использование практически не контролируемого ресурса: стека вызовов.

Во-1х, мы не можем точно знать сколько уже его использовано. Во-2х, мы не можем точно знать, сколько его еще осталось. В-3их мы не можем гарантировать доступность определённого размера этого ресурса к каждому вызову. В 4-ых, мы не можем фиксировать расход данного ресурса. Таким образом, мы попадаем в зависимость от ресурса, контролировать и распределять который чертовски сложно. В результате, мы не можем гарантировать каких либо характеристик данной функции/сервиса. Хорошо, если наш сервис работает в managed контексте: java, python, .net итп. Плохо, если сервис работает в неконтролируемой среде: javascript (с которым вообще всё плохо). Еще хуже, если сервис работает на C++, и глубина рекурсии зависит от данных, переданных пользователем.

Что же делать?

Если мы работаем не на микроконтроллере, о объёме стека можно не задумываться: для обычной цепочки вызовов его должно хватать. При условии, разумеется, что мы заботимся гигиене локальных переменных: большие объекты и массивы выделяются используя память (new/malloc). Однако использование рекурсии подразумевает, что вместо ограниченного количества вызовов, у нас их будет просто счетное.

Итак, чтобы избавиться от проблем, созданных рекурсией, можно сделать следующее (от простого к сложному):
— Жестко ограничить максимальный размер/формат/числа во входящих данных. Привет, zip бомбам и иже с ними — порой даже маленький входящий пакет может устроить большой переполох.
— Жестко ограничить максимальную глубину вызовов некоторым числом. Важно помнить, что это число должно быть ОЧЕНЬ небольшим. То есть порядка сотен. И обязательно добавить тесты, которые проверяют, что программа с этим максимальным числом не ломается. Причем с максимальным числом на всех возможных ветках исполнения (привет выделению локальных переменных по требованию). И не забывать проверять этот тест на разных опциях компилияции и после каждого билда.
— Жестко ограничить объём используемый стека. Используя сложные обходные маневры и знания о практической реализации исполнения в железе можно получить размер стека, который использован сейчас (типа взятия адреса локальной volatile переменной). В некоторых случаях (например, через libunwind в linux’е) можно получить так же доступный объём стека текущему потоку, и взять между ними разницу. При использовании подобного метода важно иметь тесты, проверяющие, что отсечение работает гарантированно и при всех вариантах входных данных — например, может получиться весело, если проверка идёт в одном методе, который рекурсивен через 3-4 других. И оно может упасть в промежуточном… Но только в режиме релиза, после inline’а некоторых функций, например. Впрочем, тут еще важны тесты на максимальную допустимую сложность, чтобы невзначай не отсечь часть корректных входных запросов, которыми клиенты реально пользуются.
— Лучший способ: избавиться от рекурсии.

И не лги, что ты волен и свят — Ты пленен и неволен.
Я раскрыл пред тобой небосвод!
Времена изменяют свой ход — Посмотри на ладони…

Беспредельная сладость свободы
Отринуть свободу
Сергей Калугин

Да-да. После постижения Дао рекурсии постигаешь так же Дао отказа от рекурсии. Практически все рекурсивные алгоритмы имеют нерекурсивные аналоги. Начиная от более эффективных (см. выше Фибоначчи), и заканчивая эквивалентными, использующими очередь в памяти вместо стека вызовов.

Каноническая нерекурсивная реализацию обхода дерева в глубину:

def printTree(node): stack = [ (node, False, False) ] while len(stack)>0: i = len(stack)-1 node, visited, opened = stack[i] if not visited: for child in reversed(node.children): if not opened: print "", del stack[i] 

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

Вот этот же код, только написанный «в лоб», сохраняя контекст (заодно, выводящий запятые между элементами):

def printTree(node): stack = [ (node, 0) ] while len(stack)>0: i = len(stack)-1 node, phase = stack[i] if phase < len(node.children): child = node.children[phase] if phase == 0: print "0: print ",", stack.append( (child, 0) ) stack[i] = (node, phase+1) else: print node.value, if phase>0: print ">", del stack[i] 

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

Злоключение

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

А как не используете рекурсию вы?

Рекурсия и стек

Если вы не новичок в программировании, то, возможно, уже знакомы с рекурсией и можете пропустить эту главу.

Рекурсия – это приём программирования, полезный в ситуациях, когда задача может быть естественно разделена на несколько аналогичных, но более простых задач. Или когда задача может быть упрощена до несложных действий плюс простой вариант той же задачи. Или, как мы скоро увидим, для работы с определёнными структурами данных.

В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.

Два способа мышления

В качестве первого примера напишем функцию pow(x, n) , которая возводит x в натуральную степень n . Иначе говоря, умножает x на само себя n раз.

pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16

Рассмотрим два способа её реализации.

    Итеративный способ: цикл for :

function pow(x, n) < let result = 1; // умножаем result на x n раз в цикле for (let i = 0; i < n; i++) < result *= x; >return result; > alert( pow(2, 3) ); // 8
function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >> alert( pow(2, 3) ); // 8

Обратите внимание, что рекурсивный вариант отличается принципиально.

Когда функция pow(x, n) вызывается, исполнение делится на две ветви:

 if n==1 = x / pow(x, n) = \ else = x * pow(x, n - 1)
  1. Если n == 1 , тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: pow(x, 1) равно x .
  2. Мы можем представить pow(x, n) в виде: x * pow(x, n — 1) . Что в математике записывается как: x n = x * x n-1 . Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на x ) и более простой аналогичной задаче ( pow с меньшим n ). Последующие шаги упрощают задачу всё больше и больше, пока n не достигает 1 .

Говорят, что функция pow рекурсивно вызывает саму себя до n == 1 .

Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – к ещё более простому и так далее, пока значение не станет очевидно.

Рекурсивное решение обычно короче

Рекурсивное решение задачи обычно короче, чем итеративное.

Используя условный оператор ? вместо if , мы можем переписать pow(x, n) , делая код функции более лаконичным, но всё ещё легко читаемым:

function pow(x, n)

Общее количество вложенных вызовов (включая первый) называют глубиной рекурсии. В нашем случае она будет равна n .

Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.

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

Контекст выполнения, стек

Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.

Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).

Контекст выполнения – специальная внутренняя структура данных, которая содержит информацию о вызове функции. Она включает в себя конкретное место в коде, на котором находится интерпретатор, локальные переменные функции, значение this (мы не используем его в данном примере) и прочую служебную информацию.

Один вызов функции имеет ровно один контекст выполнения, связанный с ним.

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

  • Выполнение текущей функции приостанавливается.
  • Контекст выполнения, связанный с ней, запоминается в специальной структуре данных – стеке контекстов выполнения.
  • Выполняются вложенные вызовы, для каждого из которых создаётся свой контекст выполнения.
  • После их завершения старый контекст достаётся из стека, и выполнение внешней функции возобновляется с того места, где она была остановлена.

Разберёмся с контекстами более подробно на примере вызова функции pow(2, 3) .

pow(2, 3)

В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3 , выполнение находится на первой строке функции.

Можно схематически изобразить это так:

Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if :

function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >> alert( pow(2, 3) );

Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:

Чтобы вычислить выражение x * pow(x, n — 1) , требуется произвести запуск pow с новыми аргументами pow(2, 2) .

pow(2, 2)

Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.

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

  1. Текущий контекст «запоминается» на вершине стека.
  2. Создаётся новый контекст для вложенного вызова.
  3. Когда выполнение вложенного вызова заканчивается – контекст предыдущего вызова восстанавливается, и выполнение соответствующей функции продолжается.

Вид контекста в начале выполнения вложенного вызова pow(2, 2) :

Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.

Когда выполнение подвызова закончится, можно будет легко вернуться назад, потому что контекст сохраняет как переменные, так и точное место кода, в котором он остановился. Слово «строка» на рисунках условно, на самом деле запоминается более точное место в цепочке команд.

pow(2, 1)

Процесс повторяется: производится новый вызов в строке 5 , теперь с аргументами x=2 , n=1 .

Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:

Теперь в стеке два старых контекста и один текущий для pow(2, 1) .

Выход

При выполнении pow(2, 1) , в отличие от предыдущих запусков, условие n == 1 истинно, поэтому выполняется первая ветка условия if :

function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >>

Вложенных вызовов больше нет, поэтому функция завершается, возвращая 2 .

Когда функция заканчивается, контекст её выполнения больше не нужен, поэтому он удаляется из памяти, а из стека восстанавливается предыдущий:

Возобновляется обработка вызова pow(2, 2) . Имея результат pow(2, 1) , он может закончить свою работу x * pow(x, n — 1) , вернув 4 .

Восстанавливается контекст предыдущего вызова:

Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8 .

Глубина рекурсии в данном случае составила 3.

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

Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.

Реализация возведения в степень через цикл гораздо более экономна:

function pow(x, n) < let result = 1; for (let i = 0; i < n; i++) < result *= x; >return result; >

Итеративный вариант функции pow использует один контекст, в котором будут последовательно меняться значения i и result . При этом объём затрачиваемой памяти небольшой, фиксированный и не зависит от n .

Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.

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

Часто код с использованием рекурсии более короткий, лёгкий для понимания и поддержки. Оптимизация требуется не везде, как правило, нам важен хороший код, поэтому она и используется.

Рекурсивные обходы

Другим отличным применением рекурсии является рекурсивный обход.

Представьте, у нас есть компания. Структура персонала может быть представлена как объект:

let company = < sales: [< name: 'John', salary: 1000 >, < name: 'Alice', salary: 600 >], development: < sites: [< name: 'Peter', salary: 2000 >, < name: 'Alex', salary: 1800 >], internals: [< name: 'Jack', salary: 1300 >] > >;

Другими словами, в компании есть отделы.

  • Отдел может состоять из массива работников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.
  • Или отдел может быть разделён на подотделы, например, отдел development состоит из подотделов: sites и internals . В каждом подотделе есть свой персонал.
  • Также возможно, что при росте подотдела он делится на подразделения (или команды). Например, подотдел sites в будущем может быть разделён на команды siteA и siteB . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.

Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?

Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл for поверх объекта company с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как sites … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.

Давайте попробуем рекурсию.

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

  1. Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
  2. Или это объект с N подотделами – тогда мы можем сделать N рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.

Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.

Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).

Алгоритм даже проще читается в виде кода:

let company = < // тот же самый объект, сжатый для краткости sales: [, ], development: < sites: [, ], internals: [] > >; // Функция для подсчёта суммы зарплат function sumSalaries(department) < if (Array.isArray(department)) < // случай (1) return department.reduce((prev, current) =>prev + current.salary, 0); // сумма элементов массива > else < // случай (2) let sum = 0; for (let subdep of Object.values(department)) < sum += sumSalaries(subdep); // рекурсивно вызывается для подотделов, суммируя результаты >return sum; > > alert(sumSalaries(company)); // 6700

Код краток и прост для понимания (надеюсь?). В этом сила рекурсии. Она работает на любом уровне вложенности отделов.

Принцип прост: для объекта <. >используются рекурсивные вызовы, а массивы [. ] являются «листьями» дерева рекурсии, они сразу дают результат.

Обратите внимание, что в коде используются возможности, о которых мы говорили ранее:

  • Метод arr.reduce из главы Методы массивов для получения суммы элементов массива.
  • Цикл for(val of Object.values(obj)) для итерации по значениям объекта: Object.values возвращает массив значений.

Рекурсивные структуры

Рекурсивная (рекурсивно определяемая) структура данных – это структура, которая повторяет саму себя в своих частях.

Мы только что видели это на примере структуры компании выше.

Отдел компании – это:

  • Либо массив людей.
  • Либо объект с отделами.

Для веб-разработчиков существуют гораздо более известные примеры: HTML- и XML-документы.

В HTML-документе HTML-тег может содержать:

  • Фрагменты текста.
  • HTML-комментарии.
  • Другие HTML-теги (которые, в свою очередь, могут содержать фрагменты текста/комментарии или другие теги и т.д.).

Это снова рекурсивное определение.

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

Связанный список

Представьте себе, что мы хотим хранить упорядоченный список объектов.

Естественным выбором будет массив:

let arr = [obj1, obj2, obj3];

…Но у массивов есть недостатки. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция arr.unshift(obj) должна переиндексировать все элементы, чтобы освободить место для нового obj , и, если массив большой, на это потребуется время. То же самое с arr.shift() .

Единственные структурные изменения, не требующие массовой переиндексации – это изменения, которые выполняются с конца массива: arr.push/pop . Таким образом, массив может быть довольно медленным для больших очередей, когда нам приходится работать с его началом.

Или же, если нам действительно нужны быстрые вставка/удаление, мы можем выбрать другую структуру данных, называемую связанный список.

Элемент связанного списка определяется рекурсивно как объект с:

  • value ,
  • next – свойство, ссылающееся на следующий элемент связанного списка или null , если это последний элемент.
let list = < value: 1, next: < value: 2, next: < value: 3, next: < value: 4, next: null >> > >;

Графическое представление списка:

Альтернативный код для создания:

let list = < value: 1 >; list.next = < value: 2 >; list.next.next = < value: 3 >; list.next.next.next = < value: 4 >; list.next.next.next.next = null;

Здесь мы можем ещё лучше увидеть, что есть несколько объектов, каждый из которых имеет value и next , указывающий на соседа. Переменная list является первым объектом в цепочке, поэтому, следуя по указателям next из неё, мы можем попасть в любой элемент.

Список можно легко разделить на несколько частей и впоследствии объединить обратно:

let secondList = list.next.next; list.next.next = null;
list.next.next = secondList;

И, конечно, мы можем вставить или удалить элементы из любого места.

Например, для добавления нового элемента нам нужно обновить первый элемент списка:

let list = < value: 1 >; list.next = < value: 2 >; list.next.next = < value: 3 >; list.next.next.next = < value: 4 >; list.next.next.next.next = null; // добавление нового элемента в список list = < value: "new item", next: list >;

Чтобы удалить элемент из середины списка, нужно изменить значение next предыдущего элемента:

list.next = list.next.next;

list.next перепрыгнуло с 1 на значение 2 . Значение 1 теперь исключено из цепочки. Если оно не хранится где-нибудь ещё, оно будет автоматически удалено из памяти.

В отличие от массивов, нет перенумерации, элементы легко переставляются.

Естественно, списки не всегда лучше массивов. В противном случае все пользовались бы только списками.

Главным недостатком является то, что мы не можем легко получить доступ к элементу по его индексу. В простом массиве: arr[n] является прямой ссылкой. Но в списке мы должны начать с первого элемента и перейти в next N раз, чтобы получить N-й элемент.

…Но нам не всегда нужны такие операции. Например, нам может быть нужна очередь или даже двухсторонняя очередь – это упорядоченная структура, которая позволяет очень быстро добавлять/удалять элементы с обоих концов, но там не нужен доступ в середину.

Списки могут быть улучшены:

  • Можно добавить свойство prev в дополнение к next для ссылки на предыдущий элемент, чтобы легко двигаться по списку назад.
  • Можно также добавить переменную tail , которая будет ссылаться на последний элемент списка (и обновлять её при добавлении/удалении элементов с конца).
  • …Возможны другие изменения: главное, чтобы структура данных соответствовала нашим задачам с точки зрения производительности и удобства.

Итого

  • Рекурсия – это термин в программировании, означающий вызов функцией самой себя. Рекурсивные функции могут быть использованы для элегантного решения определённых задач. Когда функция вызывает саму себя, это называется шагом рекурсии. База рекурсии – это такие аргументы функции, которые делают задачу настолько простой, что решение не требует дальнейших вложенных вызовов.
  • Рекурсивно определяемая структура данных – это структура данных, которая может быть определена с использованием самой себя. Например, связанный список может быть определён как структура данных, состоящая из объекта, содержащего ссылку на список (или null).

list = < value, next ->list >

Любая рекурсивная функция может быть переписана в итеративную. И это иногда требуется для оптимизации работы. Но для многих задач рекурсивное решение достаточно быстрое и простое в написании и поддержке.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *