Что такое рекурсия?
Рекурсия может показаться пугающей для новых разработчиков.
Возможно, это связано с тем, что многие ресурсы преподают его на алгоритмических примерах.
Эта статья обеспечит легкое введение в рекурсию.
Что такое рекурсия?
Рекурсия — это вызов функции из самой себя.
Он будет продолжать вызывать себя до тех пор, пока кто-нибудь не остановит его.
Рекурсивные функции имеют два случая:
- Базовый вариант — условие/предложение для завершения рекурсии.
- Рекурсивный регистр — функция вызывает сама себя.
Если у нас нет базового случая, функция будет вызывать себя бесконечно, как в приведенном ниже примере (не запускайте это), что приведет к бесконечной рекурсии:
function infiniteRecursion() {
console.log('Is this Patrick?')
console.log('No, this is Patrick!')
infiniteRecursion() //Recursive Case
}
infiniteRecursion()
/*
Expected Output:
'Is this Patrick?'
'No, this is Patrick!'
...Infinitely
*/
В приведенном выше примере мы видим, что у нас есть функция InfiniteRecursion(), которая выводит две строки:
‘Это Патрик?’
‘Нет, это Патрик!’
Затем мы выполняем рекурсию, вызывая функцию InfiniteRecursion() внутри себя, которая в этом случае будет выполнять бесконечный цикл и выводить указанные выше строки.
Как видите, рекурсивные функции позволяют выполнять задачу несколько раз.
Это в основном то, что делают циклы for/while, рекурсия — это, по сути, альтернативное решение для итерации, которое можно использовать вместо цикла.
Чтобы предотвратить бесконечную рекурсию, нам нужно добавить базовый вариант, о котором мы упоминали выше.
function countToTen(num = 1) {
console.log(num)
if (num === 10) return console.log('Complete!') //Base Case
countToTen(num + 1) //Recursive Case
}
countToTen(1)
/*
Expected Output:
1
2
3
4
5
6
7
8
9
10
Complete!
*/
В приведенной выше рекурсивной функции countToTen() был добавлен базовый случай.
Оператор if завершает функцию, если параметр num равен 10.
Если параметр num не равен 10, функция вызывает себя и передает num + 1 для увеличения счетчика, как видно на выходе.
Рекурсия против циклов
Рекурсия и циклы аналогичны тем, что они оба выполняют итерационные задачи.
Основное различие между рекурсией и циклом заключается в следующем:
- Циклы используют дополнительные переменные состояния для отслеживания и подсчета каждой итерации, чтобы отслеживать их прогресс.
- Рекурсия использует только предоставленные параметры. При каждом вызове функция передает обновленные параметры.
Ниже представлена функция ccountDownToZero(), написанная с использованием цикла for.
function countDownToZero(num = 0) {
for (let i = num; i >= 0; i--) console.log(i)
}
countDownToZero(10)
Как видите, цикл for использует переменную состояния i, для отслеживания текущего числа.
По мере повторения цикла iуменьшается, в конце концов достигая 0 и завершая цикл из-за условия остановки i ≥= 0.
Давайте сделаем то же самое ccountDownToZero(), используя рекурсию.
function countDownToZero(num = 0) {
if (num <= 0) return console.log(0) //Base Case
console.log(num)
countDownToZero(num - 1) //Recursive Case
}
countDownToZero(10)
Рекурсивной версии не нужна дополнительная переменная для отслеживания ее итеративного прогресса.
При каждом вызове параметр обновляется, в приведенном выше случае число уменьшается до тех пор, пока оно в конечном итоге не достигнет 0 и не будет удовлетворять базовому случаю num ≤= 0 и вернется.
Варианты использования для рекурсии
Есть много вариантов использования рекурсии.
Мы можем использовать его для любой итерационной задачи, алгоритмических примеров, таких как Фибоначчи, связанных списков и т. д.…
Обычный рекурсивный вопрос, который иногда появляется, — это вопрос о сбалансированных скобках.
Возьмем для примера вопрос из CodeWars.
Напишите функцию, которая составляет список строк, представляющих все способы балансировки
nпар скобок (www.codewars.com%2Fkata%2F5426d7a2c2c7784365000783%2Ftrain%2Fjavascript)
Задача здесь состоит в том, чтобы предоставить все итерации открытых и закрытых скобок ().
Примеры, которые дает вопрос CodeWars, следующие:
balancedParens(0) => [""] balancedParens(1) => ["()"] balancedParens(2) => ["()()","(())"] balancedParens(3) => ["()()()","(())()","()(())","(()())","((()))"]
Один из способов, которым мы можем решить эту проблему, — это рекурсия, как в следующем решении.
function balancedParens(n) {
const parenCombinations = []
const pushToParenCombinations = (current) => parenCombinations.push(current)
const calcParenthesesCombinations = (current, open, close) => {
if (current.length === n * 2) return pushToParenCombinations(current)
if (open < n) calcParenthesesCombinations(current + '(', open + 1, close) // Base Case
if (close < open) calcParenthesesCombinations(current + ')', open, close + 1) // Base Case
}
calcParenthesesCombinations('', 0, 0) //Recursive Case
return parenCombinations
}
Здесь у нас есть функция с именем «balancedParens()», которая принимает n пар скобок.
Массив parenCombinations будет использоваться для хранения наших комбинаций скобок, которые будут возвращены при завершении функций.
Функция pushToParenCombinations() вызывается для сохранения комбинации скобок в наш массив parenCombinations.
Наша рекурсивная функция называется calcParenthesesCombinations() и содержит три оператора if.
Первый отправляет в pushToParenCombinations() , если условие выполнено.
Второй и третий — это наши базовые случаи, которые будут либо продолжать, либо завершать рекурсивную функцию в зависимости от того, выполняется ли их соответствующее условие или нет.
Выполнение рекурсии обеспечивает более элегантный и удобочитаемый подход к решению, чем длинный цикл.
Краткое содержание
Вот оно.
Выше мы рассмотрели рекурсию в JavaScript.
Рекурсия — это вызов функции из самой себя.
Это альтернативное решение для итераций, которое можно использовать вместо цикла.
Циклы используют дополнительные переменные состояния для отслеживания итерации, тогда как рекурсия использует только параметры, предоставленные функцией.
У рекурсии есть базовый случай и рекурсивный случай.
Базовый вариант — это условие/предложение для остановки рекурсии — отсутствие добавления базового варианта приведет к бесконечной рекурсии.
Рекурсивный случай — это когда функция вызывает сама себя.
Дальнейшее чтение
Ссылки
Если у вас есть какие-либо вопросы/предложения, вы можете связаться со мной ниже:
Следуйте за мной на Medium: Люк Слоан-Балджер
