Что такое рекурсия в javascript
Рекурсия в JavaScript
Что такое рекурсия в JS? Это способность функции вызвать саму себя в своем теле. Рекурсивная функция обязательно должна иметь условие завершения, иначе мы попадем в бесконечный цикл. Случайное создание бесконечного цикла переполнит стек вызовов и браузер зависнет. Поэтому новички держатся от рекурсии подальше, на всякий случай.
Пример вызова обычной функции
Пример бесконечного цикла при вызове рекурсивной функции.
Пример демонстрирует, что если функция вызывается в теле, то после того как она отработает, все начнется сначала. Так делать не нужно.
let x = 2;
function recursion() <
x++;
recursion();
>
Как применять рекурсию в JavaScript?
С помощью рекурсии выведем в консоль числа от 3 до 6, так мы добавим в код возможность выхода из функции. Объявим глобальную переменную x со значением 3. Создадим функцию recursion(), в теле которой будем увеличивать содержимое переменной на 1 (x++) и выводить текущее значение x в консоль console.log(x). Сначала выведется число 3, к нему прибавится единица, значение переменной x станет равной 4, она также выведется на экран. Затем к 4 снова прибавится единица, значение переменной станет равной 5-ти. Это действие будет повторяться до тех пор, пока в переменной не окажется число 6. Как только нам вернется x со значением 6, работа функции завершится.
let x = 3;
function recursion() <
x++;
console.log(x);
if (x > 5) <
return x;
>
recursion();
>
recursion();
В результате в консоль выведутся следующие числа:
Пример рекурсии с массивами
Найдем сумму элементов массива при помощи рекурсии.
function summa(array, sum) <
sum += array.shift();
Функция summa первым параметром принимает массив, элементы которого мы будем суммировать при её вызове. Во второй параметр мы будем передавать результат суммы, с нулевым первоначальным значением. При помощи метода shift удаляем из массива array первый элемент и возвращает его значение. В результате изменится длина массива. Удаленный элемент присвоим переменной sum.
// текущее значение переменной sum = 1
0+1=1 // первоначальное значение + удаленный первый элемент массива
Создаем условие, где выясняем, есть ли ещё элементы в массиве? Если длина массива не равна нулю, значит, в массиве ещё есть элементы.
А на третьем проходе, тоже самое проделываем с последним элементом. Таким образом, в переменную sum перекочевали все элементы массива.
Итого
Очень часто новички боятся решать задачи с помощью рекурсий. Но к счастью, в 90% случаях в программировании на JS вполне можно обойтись без рекурсий, например, заменив их циклами. Многие так и делают, не знают и не хотят ничего знать о рекурсиях. Что нужно изучать в JavaScript, чтобы с легкостью решать при решении задач, где что применять? Советую вам подобрать такой обучающий курс, где бы автор рассказал вам то, что он использует в своей практике программирования на JavaScript. Есть толковый видеокурс, где собрана уникальная практическая информация, которая необходима Вам для успешного освоения языка JavaScript.
Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!
Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.
Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления
Если у Вас остались какие-либо вопросы, либо у Вас есть желание высказаться по поводу этой статьи, то Вы можете оставить свой комментарий внизу страницы.
Порекомендуйте эту статью друзьям:
Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):
Комментарии ( 0 ):
Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.
Copyright © 2010-2021 Русаков Михаил Юрьевич. Все права защищены.
Что такое рекурсия в javascript
В теле функции могут быть вызваны другие функции для выполнения подзадач.
Рекурсия используется для ситуаций, когда выполнение одной сложной задачи можно представить как некое действие в совокупности с решением той же задачи в более простом варианте.
Сейчас мы посмотрим примеры.
Эта глава предназначена для читателей, которые пока с этой темой незнакомы и хотят лучше разобраться в том, как работают функции.
Степень pow(x, n) через рекурсию
Её можно представить как совокупность более простого действия и более простой задачи того же типа вот так:
Этот алгоритм на JavaScript:
Общее количество вложенных вызовов называют глубиной рекурсии. В случае со степенью, всего будет n вызовов.
Максимальная глубина рекурсии в браузерах ограничена, точно можно рассчитывать на 10000 вложенных вызовов, но некоторые интерпретаторы допускают и больше.
Контекст выполнения, стек
Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого мы рассмотрим, как вообще работают функции, что происходит при вызове.
У каждого вызова функции есть свой «контекст выполнения» (execution context).
Затем интерпретатор приступает к выполнению вложенного вызова.
Разберём происходящее с контекстами более подробно, начиная с вызова (*) :
Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.
Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.
Реализация возведения в степень через цикл гораздо более экономна:
Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Но переделка рекурсии в цикл может быть нетривиальной, особенно когда в функции, в зависимости от условий, используются различные рекурсивные подвызовы, когда ветвление более сложное.
Есть и другие применения, с которыми мы встретимся по мере изучения JavaScript.
Здесь мы постарались рассмотреть происходящее достаточно подробно, однако, если пожелаете, допустимо временно забежать вперёд и открыть главу info:debugging-chrome, с тем чтобы при помощи отладчика построчно пробежаться по коду и посмотреть стек на каждом шаге. Отладчик даёт к нему доступ.
Функциональное программирование с точки зрения EcmaScript. Рекурсия и её виды
Сегодня мы продолжим наши изыскания на тему функционального программирования в разрезе EcmaScript, на спецификации которого основан JavaScript. В предыдущих статьях цикла были рассмотрены следующие темы:
Рекурсия
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее применение находит в математике и информатике.
Применительно к программированию под рекурсией подразумевают процессы, которые вызывают сами себя в своём теле. Рекурсивная функция имеет несколько обязательных составляющих:
Выделим характерные составляющие рекурсивной функции. Терминальное условие
и правило движения по рекурсии
Важно осознавать, что рекурсия это не какая-то специфическая фича JS, а техника очень распространённая в программировании.
Рекурсивный и итеративный процессы
Рекурсию можно организовать двумя способами: через рекурсивный процесс или через итеративный.
Рекурсивный процесс мы с вами уже видели:
Итеративное решение задачи о факториале выглядело бы так:
Оба этих варианта это рекурсия. В обоих решениях есть характерные для рекурсии черты: терминальное условие и правило движения по рекурсии. Давайте разберём их отличия.
Рекурсивный процесс на каждом шаге запоминает действие. которое надо сделать. Дойдя до термального условия, он выполняет все запомненные действия в обратном порядке. Поясним на примере. Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вглубь больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.
Выглядит это примерно так:
Как видите, основная идея рекурсивного процесса — откладывание вычисления до конца.
Такой процесс порождает изменяемое во времени состояние, которое хранится «где-то» снаружи текущего вызова функции.
Думаю, вы помните, что в первой статье из цикла о Функциональном программировании мы говорили о важности имутабельности и отсутствия состояния. Наличие состояния порождает много проблем, с которыми не всегда легко справится.
Итеративный процесс отличается от рекурсивного фиксированным количеством состояний. На каждом своём шаге итеративный процесс считает всё, что может посчитать, поэтому каждый шаг рекурсии существует независимо от предыдущего.
Думаю, очевидно, что итеративный процесс потребляет меньше памяти. Следовательно, всегда при создании рекурсии следует использовать его. Единственное исключение: если мы не можем посчитать значение до достижения термального условия.
Древовидная рекурсия
Многие считают, что деревья и работа с ними это что-то очень заумное, сложное и не понятное простым смертным. На самом деле это не так. Любая иерархическая структура может быть представлена в виде дерева. Даже человеческое мышление подобно дереву.
Чтобы лучше понять древовидную рекурсию разберём простой и популярный пример — числа Фибоначчи.
Чи́сла Фибона́ччи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS), в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).
Математически довольно просто сформулировать описание (а ведь декларативное программирование и есть описание) данной последовательности:
Теперь давайте перейдём от математики к логическим рассуждениям(нам ведь нужно программную логику написать). Для вычисления fib(5) нам придётся вычислить fib(4) и fib(3). Для вычисления fib(4) нам придётся вычислить fib(3) и fib(2). Для вычисления fib(3) нам придётся вычислить fib(2) и так до тех пор пока мы не дойдём до известных значений (1) и (2) в нашей математической модели.
На какие мысли нас должны навести наши рассуждения? Очевидно, мы должны использовать рекурсию. Термальное условие можно сформулировать как n
Рекурсия и стек
Вернёмся к функциям и изучим их более подробно.
Нашей первой темой будет рекурсия.
Если вы не новичок в программировании, то, возможно, уже знакомы с рекурсией и можете пропустить эту главу.
Рекурсия – это приём программирования, полезный в ситуациях, когда задача может быть естественно разделена на несколько аналогичных, но более простых задач. Или когда задача может быть упрощена до несложных действий плюс простой вариант той же задачи. Или, как мы скоро увидим, для работы с определёнными структурами данных.
В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.
Два способа мышления
Рассмотрим два способа её реализации.
Итеративный способ: цикл for :
Рекурсивный способ: упрощение задачи и вызов функцией самой себя:
Обратите внимание, что рекурсивный вариант отличается принципиально.
Когда функция pow(x, n) вызывается, исполнение делится на две ветви:
Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:
Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – к ещё более простому и так далее, пока значение не станет очевидно.
Рекурсивное решение задачи обычно короче, чем итеративное.
Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.
Это ограничивает применение рекурсии, но она всё равно широко распространена: для решения большого числа задач рекурсивный способ решения даёт более простой код, который легче поддерживать.
Контекст выполнения, стек
Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.
Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).
Контекст выполнения – специальная внутренняя структура данных, которая содержит информацию о вызове функции. Она включает в себя конкретное место в коде, на котором находится интерпретатор, локальные переменные функции, значение this (мы не используем его в данном примере) и прочую служебную информацию.
Один вызов функции имеет ровно один контекст выполнения, связанный с ним.
Когда функция производит вложенный вызов, происходит следующее:
pow(2, 3)
Можно схематически изобразить это так:
Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if :
Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:
pow(2, 2)
Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.
Вид контекста в начале выполнения вложенного вызова pow(2, 2) :
Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.
Когда выполнение подвызова закончится, можно будет легко вернуться назад, потому что контекст сохраняет как переменные, так и точное место кода, в котором он остановился. Слово «строка» на рисунках условно, на самом деле запоминается более точное место в цепочке команд.
pow(2, 1)
Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:
Выход
Когда функция заканчивается, контекст её выполнения больше не нужен, поэтому он удаляется из памяти, а из стека восстанавливается предыдущий:
Восстанавливается контекст предыдущего вызова:
Глубина рекурсии в данном случае составила 3.
Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.
Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.
Реализация возведения в степень через цикл гораздо более экономна:
Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Но переделка рекурсии в цикл может быть нетривиальной, особенно когда в функции в зависимости от условий используются различные рекурсивные подвызовы, результаты которых объединяются, или когда ветвление более сложное. Оптимизация может быть ненужной и совершенно нестоящей усилий.
Часто код с использованием рекурсии более короткий, лёгкий для понимания и поддержки. Оптимизация требуется не везде, как правило, нам важен хороший код, поэтому она и используется.
Рекурсивные обходы
Другим отличным применением рекурсии является рекурсивный обход.
Представьте, у нас есть компания. Структура персонала может быть представлена как объект:
Другими словами, в компании есть отделы.
Отдел может состоять из массива работников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.
Также возможно, что при росте подотдела он делится на подразделения (или команды).
Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?
Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл for поверх объекта company с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как sites … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.
Давайте попробуем рекурсию.
Как мы видим, когда наша функция получает отдел для подсчёта суммы зарплат, есть два возможных случая:
Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.
Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).
Рекурсия
Время чтения: больше 15 мин
Обновлено 27 октября 2021
Кратко
Рекурсия — это что-то, что описывает само себя.
Представить рекурсию проще всего на примере зеркального коридора — когда напротив друг друга стоят два зеркала. Если посмотреть в одно, то в нём будет отражение второго, во втором — отражение первого и так далее.
В «Начале» Нолана есть момент с зеркальным коридором, когда в отражении зеркала видно отражение зеркала, в котором видно отражение зеркала, в котором видно.
Второй пример, чуть более академически правильный — это фрактал. Тот же треугольник Серпинского — это пример рекурсии, потому что часть фигуры — это одновременно вся фигура.
Треугольник состоит из 3 точно таких же треугольников.
Рекурсия в программировании
В программировании под рекурсией чаще всего понимают функцию, которая вызывает саму себя.
При решении некоторых задач мы можем обнаружить, что решение можно разбить на несколько простых действий и более простой вариант той же задачи.
Например, при возведении числа в степень мы берём число, умножаем его на себя несколько раз. Эту операцию можно представить в виде:
Но это же можно представить в виде нескольких последовательных умножений на 2:
При таком представлении всё возведение в степень — это лишь умножение предыдущего результата на 2:
Именно такие задачи называются рекурсивными — когда часть условия ссылается на всю задачу в целом (или похожую на неё).
У рекурсии 2 составляющие: повторяющиеся операции и базовый случай.
Повторяющиеся операции
В примере с возведением в степень повторяющиеся операции — это умножение.
Такие операции могут быть сложными и включать в себя несколько подзадач. Такое, например, часто встречается в математике.
Базовый случай
Вторая важная часть рекурсии — это базовый случай.
Базовый случай — это условие, при выполнении которого рекурсия заканчивается и функция больше не вызывает саму себя.
Например, при возведении в степень базовый случай наступает, когда значение степени становится равно искомому.
Как только выполнение доходит до базового случая, оно останавливается.
Без базового случая любая рекурсивная функция уйдёт в бесконечное выполнение, потому что будет вызывать себя без конца.
В JS это приводит к переполнению стека вызовов, и функция останавливается с ошибкой.
Если выполнить функцию без базового случая, которая лишь вызывает себя, получим ошибку.
Цикл и рекурсия
Из-за повторяющихся операций рекурсия схожа с циклом. Их часто считают взаимозаменяемыми, но это всё же не совсем так.
Рекурсия проигрывает циклу в следующем:
Цикл же проигрывает рекурсии в таких вещах:
Поэтому на вопрос «Что использовать: рекурсию или цикл?» ответом будет «Зависит от задачи», серебряной пули здесь нет :–)
Давайте решим одну и ту же задачу с использованием цикла и рекурсии, чтобы увидеть разницу в подходах. Будем писать функцию для нахождения факториала.
Факториал числа — это произведение всех чисел от единицы до этого числа. Например, факториал 5 — это произведение (1 × 2 × 3 × 4 × 5) = 120.
Факториал с помощью цикла
Сперва решим задачу нахождения факториала с помощью цикла.
В этой функции мы используем цикл, чтобы умножить каждое число на результат предыдущего умножения. То же самое мы можем сделать и рекурсивно.
Факториал с помощью рекурсии
Для расчёта факториала рекурсивно мы создадим функцию, в которой в первую очередь опишем базовый случай, а уже потом — повторяющиеся действия.
Хорошим правилом при работе с рекурсией считается первым делом описывать базовый случай (как ранний выход, early return) и только потом — всё остальное. Это позволяет сделать работу с рекурсией безопаснее.
В виде блок-схемы мы можем представить алгоритм факториала как условие и под-вызов той же функции.
Кроме того, что функция стала заметно короче, она теперь выражает непосредственно математическую суть факториала.
Разберём по шагам, что происходит с переменной n и результатом функции factorial после каждого вызова:
Минусы такой реализации:
Рекурсивные структуры данных
Раньше мы упомянули, что в программировании чаще всего под рекурсией понимают функцию, которая вызывает сама себя. Но кроме рекурсивных функций ещё есть рекурсивные структуры данных.
Структура данных — это контейнер, который хранит данные в определённом формате. Этот контейнер решает, каким образом внешний мир может эти данные считать или изменить.
Структуры данных, части которых включают в себя такие же структуры, называются (вы угадали) рекурсивными. Работать с такими структурами в цикле не очень удобно. Чтобы понять почему, рассмотрим пример одной из рекурсивных структур данных — дерева.
Деревья
Дерево — это структура, в которой у каждого узла может быть несколько дочерних подузлов — «детей».
Мы уже встречались с деревьями в статье «Как браузер рисует страницы». Мы рассматривали DOM, CSSOM и Render Tree. Вспомним, как выглядит DOM-дерево.
Работать с деревьями с помощью циклов (итеративно) неудобно. Представьте, что мы хотим получить названия всех элементов на странице. Да, мы можем пройтись циклом по 1-му уровню или 2-му, но дальше нужно думать, как определять, где мы были, где ещё нет и куда идти дальше.
С рекурсией обход дерева становится немного проще.
Рекурсивный обход
В случае с рекурсией мы можем придумать например такой алгоритм для обхода дерева:
Когда использовать рекурсию
Сама по себе рекурсия — это всего лишь инструмент. Нет чётких правил, когда её надо использовать, а когда — нет. Есть лишь некоторые рекомендации.