Рекурсия в JavaScript
Рекурсия в общем смысле — это повторение какого-либо объекта или процесса внутри самого этого объекта или процесса.
В программировании в том числе и в JavaScript под рекурсией чащего всего понимают метод, который предполагает создание функции, которая вызывает саму себя до тех пор пока программа не достигнет необходимого результата.
Рассмотрим простой пример
let days = 0; function howMuchToLearnJS() < days++; console.log(days); howMuchToLearnJS(); >howMuchToLearnJS(); В данном примере мы написали функцию, которая:
- берет переменную days ;
- увеличивает ее на единицу;
- выводит результат в console;
- вызывает функцию howMuchToLearnJS() , тоесть саму себя.
В результате мы получим рекурсию и в дополнение «бесконечный» вывод чисел, каждое из которых будет больше на 1-цу предыдущего. Однако есть такое понятие, как стек, который рассчитан на ограниченное количество вложенных вызовов. В итоге, где-то на 11 тысячах вывод прекратиться и console выдаст ошибку Uncaught RangeError: Maximum call stack size exceeded — превышен максимальный размер стека вызовов.
Для того, чтобы такой ситуации не произошло в рекурсивной функции прописывают базовый случай — условие, когда выполнение программы должно закончится. Для большей надежности рекомендуют сначала прописать условие выхода, а затем описывать функционал.
let days = 0; function howMuchToLearnJS() < if (days === 400) return; // условие выхода days++; console.log(days); howMuchToLearnJS(); >howMuchToLearnJS(); Цикл и рекурсия
Любая задача, которую можно решить рекурсией, также решается и с помощью цикла. Перепишим наш пример.
Тут возникает вопрос, зачем использовать рекурсию, когда можно обойтись циклом. Дело в том, что в разных ситуациях один метод можно применять с большей эффективностью, чем другой и наоборот.
- легче обходить вложенные структуры;
- чаще всего код получается короче, легче для понимания и поддержки.
Точного ответа, что лучше цикл и рекурсия нет. Все зависит от конкретной задачи.
Контекст выполнения и стек
Контекст выполнения — это структура данных, содержащая информацию о вызываемой функции. Другими словами, когда функция запускается, создается контекст, в который записывается все относящееся к вызываемой программе от переменных до того места где находился интерпретатор, когда она была вызвана.
Стек в случае с рекурсией — это специальная структура данных в которую записывается по порядку информация о каждом вызове функции самой себя, в том числе и первом вызове.
Отсюда исходит основная опасность работы с рекурсией — это переполнение стека. Глубина рекурсии равняется количеству контекстов, которые хранятся в стеке одновременно, а это число ограничено мощностью компьютера — обычно от 10 000 до 12 000. Для недопущения переполнения и существует базовый случай, тоесть условие, когда вызов функции самой себя должен прекратиться.
Факториал
Разбавим теорию популярным примером и напишим функцию вычисляющую факториал.
Факториал — это произведение всех натуральных чисел от 1 до заданного включительно.
let s = 1; function calcFactorial(n) < if (n === 0) return; s = s * n; calcFactorial(n - 1); >calcFactorial(10); console.log(s); function calcFactorial(n) < if (n return n * calcFactorial(n - 1); > console.log(calcFactorial(10)); function calcFactorial(n) < let s = 1; for (let i = 1; i console.log(s); > calcFactorial(10); Сложные структуры и рекурсия
Объекты с неизвестной глубиной вложенности — это классический пример, когда с помощью рекурсии задачу решить намного легче, чем с помощью цикла.
let jsUniversity = < javascript: [< name: 'Дмитрий', payment: 20000, >, < name: 'Ольга', payment: 20000 >, < name: 'Вероника', payment: 20000 >], react: < 'full time': [< name: 'Татьяна', payment: 30000, >, < name: 'Витор', payment: 30000, >], extramural: [< name: 'Павел', payment: 25000, >, < name: 'Денис', payment: 25000, >] > >; function income(devUniversity) < if (Array.isArray(devUniversity)) < return devUniversity.reduce((prev, current) =>prev + current.payment, 0); > else < let sum = 0; for (let extramural of Object.values(devUniversity)) < sum += income(extramural); >return sum; > > alert(income(jsUniversity)); На входе объект с несколькими уровнями вложенности — стоит задача рассчитать доход университета со всех учеников. Если глубина структуры заранее известна, найти нужные элементы с помощью цикла не так уж и сложно, но как только появится дополнительная глубина, программу придется дописывать. В нашем случае доход рассчитан с помощью рекурсии, при добавлении новых направлений или групп, код продолжил работать корректно.
Итого
Рекурсия — это метод написания функции, когда она вызывает саму себя. С помощью рекурсии можно решить много задач, но большинство из них можно легко переписать используя цикл.
Структуры данных с глубокой вложенностью или неизвестной глубиной — отличный пример, когда рекурсия справляется с обходом лучше, чем цикл.
Базовый случай — это условие, когда рекурсия должна закончится. Такое условие важно предусмотреть, так как количество вызовов функции самой себя ограничено из-за переполнения стека.
Skypro — научим с нуля
Понимание рекурсии с помощью JavaScript
Alberta Williams Last updated Mar 21, 2022
Введение
Некоторые проблемы более естественным образом решаются с помощью рекурсии. Например, последовательность, подобная последовательности Фибоначчи, имеет рекурсивное определение. Каждое число в последовательности представляет собой сумму двух предыдущих чисел в последовательности. Проблемы, которые требуют, чтобы вы построили или пересекли древовидную структуру данных, также могут быть решены с помощью рекурсии. Обучение думать рекурсивно даст вам мощное умение решать такие проблемы.
В этом уроке я шаг за шагом приведу несколько рекурсивных функций, чтобы увидеть, как они работают, и показать методы, которые вы можете использовать для систематического определения рекурсивных функций.
Содержание:
- Что такое рекурсия?
- Рекурсия с цифрами
- Рекурсия со списками
- Построение списков
- Обзор
Что такое рекурсия?
Рекурсивно определенная функция — это функция, которая определяется в терминах более простой версии самого себя. Это упрощенный пример:
Чтобы понять, как рекурсия работает концептуально, мы рассмотрим пример, который не имеет никакого отношения к коду. Представьте, что вы отвечаете за ответы на телефонные звонки на работе. Поскольку это занятая компания, ваш телефон имеет несколько телефонных линий, поэтому вы можете одновременно манипулировать несколькими вызовами. Каждая телефонная линия — это кнопка на ресивере, и при входящем вызове кнопка будет мигать. Сегодня, когда вы приходите на работу и включаете телефон, сразу появляются четыре строки. Поэтому вы можете отвечать на все вызовы.
Вы берете линию один и говорите им «пожалуйста, держитесь». Затем вы берете линию два и ставите их на удержание. Затем вы поднимаете линию три и помещаете их в режим ожидания. Наконец, вы отвечаете на четвертую строку и говорите с вызывающим. Когда вы закончите с четвертым абонентом, вы повесите трубку и возьмете третий звонок. Когда вы закончите с третьим вызовом, вы повесите трубку и возьмете второй звонок. Когда вы закончите со вторым вызовом, вы повесите трубку и заберете первый звонок. Когда вы закончите этот звонок, вы можете, наконец, положить телефон.
Каждый из телефонных звонков в этом примере подобен рекурсивному вызову функции. Когда вы получаете звонок, он помещается в стек вызовов (в терминах кода). Если вы не можете выполнить звонок сразу, вы переводите вызов на удержание. Если у вас есть вызов функции, который не может быть сразу оценен, он остается в стеке вызовов. Когда вы можете ответить на звонок, он подбирается. Когда ваш код способен оценивать вызов функции, он выгружается из стека. Соблюдайте эту аналогию, просматривая приведенные ниже примеры кода.
Рекурсия с цифрами
Все рекурсивные функции нуждаются в базовом случае, чтобы они завершились. Однако просто добавление базового футляра к нашей функции не препятствует его бесконечному выполнению. Функция должна иметь шаг, чтобы приблизить нас к основному случаю. Последний — это рекурсивный шаг. На рекурсивном шаге проблема сводится к меньшей версии проблемы.
Предположим, что у вас есть функция, которая будет суммировать числа от 1 до n. Например, если n = 4, сумма будет равна 1 + 2 + 3 + 4.
Сначала мы определяем базовый случай. Обнаружение базового случая можно также рассматривать как поиск случая, когда проблема может быть решена без рекурсии. В этом случае, когда n равно нулю. 0 не имеет частей, поэтому наша рекурсия может остановиться, когда мы достигнем 0.
На каждом шаге вы будете вычитать один из текущего числа. Что такое рекурсивный случай? Рекурсивный случай — это сумма функций, называемая сокращенным числом.