Я случайно наткнулся на этот термин, когда выполнял некоторые упражнения с JavaScript, и мне стало любопытно. Кажется, существует довольно много споров об использовании циклов и использовании рекурсивной функции. Итак, в этой статье я постараюсь изо всех сил объяснить свои знания о рекурсии и о том, когда она используется.
В рекурсии есть популярное высказывание, что для того, чтобы понять рекурсию, вы должны сначала понять рекурсию. Но это не совсем так, потому что, чтобы по-настоящему понять рекурсию, вы должны сначала понять, что такое стек.
Стеки — это простейшая структура данных в информатике. Это структура данных, которая содержит последовательность данных и позволяет вам взаимодействовать только с самым верхним элементом. Думайте о стопках, как о карточных пасьянсах. Вы можете добавлять или удалять карты только с самого верха. То же самое и со стеками. Они следуют принципу LIFO (последним пришел, первым ушел).
Обычно мы добавляем или удаляем что-то из стека. Добавление в верхнюю часть стека называется проталкиванием. В то время как удаление чего-либо из вершины стека называется выталкиванием.
Итак, разобравшись со стеками, давайте углубимся в рекурсию. Рекурсия — это функция, которая вызывает себя до тех пор, пока не достигнет базового условия и не выйдет из цикла. В рекурсивной функции есть 2 части: базовый случай и рекурсивный случай. Базовый случай важен, чтобы избежать бесконечного повторения функции, что вызовет «переполнение стека». С другой стороны, рекурсивный случай написан так, что во время повторных вызовов он сводится к базовому случаю (или приближает вас к базовому случаю).
Например, если вы хотели «доесть целый торт». Используя рекурсивный метод, ваши шаги будут выглядеть так:
- Если торта больше нет, прекратите есть.
2. иначе возьми один кусок торта и съешь его
3. повторяйте шаг 2, пока не «найдёте весь торт»
Шаг 1 — это наше базовое условие. Он говорит вам прекратить повторять действие, если это базовое условие выполнено. Шаг 2: если торт остался, выполните простое действие, которое упростит решение ситуации, а именно съешьте торт по кусочку за раз. Наконец, повторяйте все шаги, пока не закончите весь торт.
Это приводит нас к наиболее важному варианту использования рекурсии: решать сложные проблемы, разбивая их на более мелкие, более простые, повторяющиеся задачи, когда они носят рекурсивный характер.
Давайте посмотрим на другой пример. Здесь мы рассмотрим факториалы.
5! = 5 x 4 x 3 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4! = 5 x 24 = 120
В приведенном выше примере мы видим, что факториал имеет рекурсивный характер, потому что 5! то же самое, что 5 х 4!. Исходя из этих знаний, мы можем написать код, как показано ниже:
функция факт(п) {
вернуть n * факт (n — 1); // рекурсивный случай
}
Но это вернет ошибку, потому что функция просто продолжит вызывать себя и не остановится, пока не достигнет переполнения стека. Таким образом, нам нужно будет добавить базовое условие. Базовое условие/базовый случай — это набор обстоятельств, при которых рекурсивная функция перестанет повторяться.
В этом примере наш базовый случай — когда n = 1, мы возвращаем 1, потому что 1! = 1.
функция факт(п) {
if (n > 1) {
вернуть n * факт (n — 1); // рекурсивный случай
} еще {
вернуть 1; //базовый вариант
}
}
Вот лучшая визуализация того, как вызывается наш fact() с точки зрения стеков вызовов.
Например, если мы хотим найти значение факта (5), так как 5 > 1, он вернет 5 x 4!. Теперь нам нужно снова вызвать fact(). Мы помещаем новый объект поверх стека вызовов. И в этом объекте мы вызываем fact(4), так как 4 > 1, он вернет 4 x 3! и так далее, пока не будет достигнут факт (1), который является нашим базовым случаем, поэтому ему больше не нужно делать рекурсию. Теперь мы возвращаемся, что означает, что мы извлекаем объекты из стека вызовов. Итак, теперь мы знаем, что 2! равно 2, мы можем подставить это значение обратно в 3! = 3 x 2 и так далее, пока мы не назовем 5! который в конечном итоге вернет значение 120.
Каждая рекурсивная функция всегда должна иметь по крайней мере один базовый случай, иначе она будет продолжать рекурсию вечно и вызывать переполнение стека, и один рекурсивный случай, потому что в противном случае это не рекурсивная функция, если она не вызывает себя.
Сказав это, мы действительно можем использовать цикл для решения этого факториального примера, который также довольно читабелен и прост в написании. Нет ничего такого, что могла бы сделать рекурсия, чего нельзя было бы сделать с помощью цикла. Это приводит к следующему вопросу…
Когда нужно использовать рекурсию?
Если рекурсия не более эффективна, чем цикл, и часто ее сложнее понять, зачем нам вообще использовать рекурсию?
Рекурсия действительно полезна при работе с деревьями или древовидной структурой, такой как файловая система, потому что они рекурсивны по своей природе.
