Что такое рекурсия в программировании
Перейти к содержимому

Что такое рекурсия в программировании

  • автор:

Рекурсия — Python: Функции

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

Что такое рекурсия

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

Это работает и в Python. Обычно в определении функции можно использовать только определения, которые дали ранее. Но есть одно исключение — функция в своем теле может вызывать себя. Выглядит это так:

def factorial(n): if n  0: return 1 return n * factorial(n - 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py

Эта функция вычисляет факториал числа n через умножение числа на факториал числа n — 1 .

Условие завершения рекурсии

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

В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:

  • По рекурсивной — в этой ветке произойдет вызов себя
  • По терминальной — закончит вычисление и вернет результат

Какой-то из аргументов рекурсивной функции должен обязательно убывать. В качестве убывания может быть:

  • Уменьшение счетчика
  • Отбрасывание головы списка при движении к его хвосту
  • Вызов себя для части исходной структуры при обработке древовидных структур данных

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

Переполнение стека

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

Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.

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

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

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

Так выглядит переполнение стека при подсчете факториала:

factorial(1000) # Traceback (most recent call last): # File "", line 1, in # File "", line 4, in factorial # File "", line 4, in factorial # File "", line 4, in factorial # [Previous line repeated 995 more times] # File "", line 2, in factorial # RecursionError: maximum recursion depth exceeded in comparison 

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

Зачем нужна рекурсия

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

Виды рекурсии

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

  • Прямая — когда функция вызывает себя
  • Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую

Так же рекурсии можно разделить по количеству рекурсивных вызовов:

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

Рассмотрим подробнее линейную и каскадную рекурсию.

Пример линейной рекурсии

Если рекурсия в функции проверяет Гипотезу Коллатца , она считается линейной:

def collatz(n): if n == 1: return True if n % 2 == 0: return collatz(n // 2) return collatz(n * 3 + 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py

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

Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:

  • Начало (голову)
  • Остальную часть коллекции (хвост)

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

 [1, [2, 3]] -> [1, [2, [3]]] -> [1, [2, [3, []]]] 

При рекурсивной обработке коллекции мы будем обходить коллекцию и дробить старый хвост на новую голову и новый хвост на каждой итерации. Так мы делаем до тех пор, пока не получим пустой хвост — то есть конец коллекции:

# Функция рекурсивно обходит список, суммируя числа из него def sum(array): # Мы можем использовать оператор упаковки для записи в хвост остальной части списка head, *tail = array if not tail: return head return head + sum(tail) 

Пример каскадной рекурсии

Если рекурсия в функции вычисляет очередное Число Фибоначчи , она называется каскадной:

def fibonacci(n): if n  2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py

Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.

Открыть доступ

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

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

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

Что такое рекурсия, рекурсивный и итеративный процесс в программировании

Что такое рекурсия, рекурсивный и итеративный процесс в программировании главное изображение

Рекурсия vs рекурсивный или итеративный процесс: в чем разница

Рекурсия — это функция, которая вызывает саму себя, но с другими значениями параметров.

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

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

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

Бесплатные курсы по программированию в Хекслете

  • Освойте азы современных языков программирования
  • Изучите работу с Git и командной строкой
  • Выберите себе профессию или улучшите навыки

Методы решения задач с помощью рекурсии

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

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

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

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

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

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

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

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

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

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

А на этой картинке видно, что использование памяти не растет.

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

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

Что такое рекурсивные функции и в чем особенность их применения

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

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

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

Читайте также: Как проверить качество кода: функциональное и нефункциональное тестирование

В контексте каждого рекурсивного вызова такой функции хранится вся необходимая информация для его успешного выполнения. Он самодостаточен и никак не зависит от предыдущих контекстов. Помните, что этот чувак ничего не откладывает на потом, на вечер пятницы?

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

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

Что такое хвостовая рекурсия

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

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

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

Бесплатные курсы по программированию в Хекслете

  • Освойте азы современных языков программирования
  • Изучите работу с Git и командной строкой
  • Выберите себе профессию или улучшите навыки

Рекурсия в программировании

Рекурсия в программировании

Довольно давно, в программировании появился термин «рекурсия«, что означает вызов функции (или же процедуры) непосредственно из самой себя. Есть простая (непосредственная) рекурсия или рекурсия, которая работает через другие процедуры и функции (такой вид называется косвенной, сложной рекурсией).

  • треугольник Серпинского;
  • эффект Дросте;
  • вычисление факториала.

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

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

procedure Rec1(f: integer); begin// объявление начала процедуры if (f>0) then //задается условие Rec1(f-1); writeln(f); end;// конец процедуры

Пример рекурсии

Кроме того, в функциональных языках в чистом виде (к ним относятся Пролог, Haskell) невозможно задать цикл синтаксически, поэтому рекурсия является единственным доступным средством задания повторяющихся вычислений. Но иногда, следует избегать рекурсивных конструкций в программных модулях, потому что они могут стать причиной излишне глубокой рекурсии. В языках С++/С# функции имеют возможность вызова самих себя.

Дадим определение рекурсивной функции— это функция, в теле которой оператор вызывает функцию, которую содержит данный оператор.

Самым распространенным примером рекурсии служит известная функция вычисления факториала factоr(). Факториал некоторого числа это произведение чисел от 1 до этого числа.

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

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

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

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

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

В качестве первого примера напишем функцию 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 не будет опубликован. Обязательные поля помечены *