Рекурсия простыми словами

3548
рекурсия на примере русской матрешки
рекурсия на примере русской матрешки

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

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

Рекурсия простыми словами
Рекурсия простыми словами

Вы понимаете, что, открыв эту куклу, вы можете открыть еще одну, точно такую же, только чуть меньше! Так продолжается до тех пор, пока вы не дойдете до последней куклы, и тогда цикл прерывается. Это наглядное представление рекурсии!

рекурсия на примере русской матрешки
рекурсия на примере русской матрешки

Не приведёт ли рекурсивная функция к бесконечному циклу?

Это вполне возможно! Однако, как и у функции for или while, рекурсию можно прервать условием break, чтобы функция перестала вызывать саму себя.

Вот простой пример функции обратного отсчета с использованием рекурсии:

function countDown(n){
console.log(n)
if(n > 1){
countDown(n -1) // recursive call
} else {
return true // base case
}
}
countDown(5)
// 5
// 4
// 3
// 2
// 1
countDown(-1)
// - 1 
// true

Как прервать рекурсию?

У нас есть функция countDown, которая принимает аргумент (n). Мы хотим, чтобы наш код воспроизводил обратный отсчет. Поэтому мы создаем условие:

Если (n) больше 1, то вызвать функцию CountDownи вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1.

По умолчанию мы также должны создать базовое условие, чтобы предотвратить попадание в бесконечный цикл, — это наш оператор return true. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.
Проще говоря, наш код делает следующее:

countDown(5)
 countDown(4)
  countDown(3)
   countDown(2)
    countDown(1)
    return
   return
  return
 return
return

Так в чем же плюсы и минусы рекурсивных функций?

Хороший вопрос! Чтобы лучше ответить на него, давайте рассмотрим плюсы и минусы выполнения рекурсивного кода!

Плюсы:

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

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

Хотя я хотел бы добавить, что рекурсия не всегда будет самым быстрым вариантом по сравнению с итерацией!

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

 

Минусы:

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

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

Что это за «стек», о котором вы упомянули?

Отличный вопрос!

Стек — это структура данных, которая работает по принципу «последний вошел — первый вышел». Элемент «заталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.- freecodecamp

Стек хорошо тем, что он очень быстрый!Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции pop(), push() и empty().

Стек на примере Лего
Стек на примере Лего

Так стоит ли использовать рекурсию вместо итерации?

Оба метода одинаково эффективны для решения проблем, однако, отвечая на ваш вопрос, можно сказать, что это зависит от поставленной перед вами задачи!
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Итерации (циклы) столь же эффективны в плане скорости и оптимизации, они занимают меньше места в стеке, а их читабельность проще для понимания, поскольку они более четко показывают, что происходит в цикле.