Я только недавно закончил учебный лагерь по разработке программного обеспечения и начал самостоятельно изучать структуры данных и алгоритмы. Сейчас они довольно сложны, но при достаточной практике я знаю, что мне понравится их решать! Здесь я собираюсь рассказать о рекурсии и о том, что я уже узнал о ней, на нескольких примерах.
Кое-что забавное, о чем я узнал, это то, что если вы введете в Google запрос «рекурсия», вы получите всплывающее сообщение: «Вы имели в виду: рекурсия». Затем, когда вы нажимаете на эту ссылку, она снова показывает то же сообщение. Вот что такое рекурсия — вызов чего-то снова и снова. В основном мы используем рекурсию, чтобы разбить большую проблему на несколько более мелких.
Рекурсивная функция — это функция, которая продолжает вызывать себя (каждый раз с меньшими входными данными), пока что-то не остановит ее, выполнив какое-то условие. Это условие известно как базовый вариант. Базовый вариант сообщает функции, в какой момент она должна прекратить вызывать себя. Без базового случая вы просто застрянете в бесконечном цикле, который в JavaScript известен как переполнение стека. Объявление условия для завершения функции чрезвычайно важно, чтобы убедиться, что вы не переполняете стек. В большинстве случаев это просто объявляется внутри оператора if в начале функции.
Теперь, когда я дал базовое изложение рекурсии, я хочу привести пример функции с циклом, а затем с рекурсией, чтобы показать вам, как обе функции могут привести к одному и тому же результату.
В моем примере мы просто собираемся упростить задачу и написать функцию countDown, которая принимает число. Функция должна выполнить console.log это число, а затем каждое число, меньшее его, до нуля.
Вот пример без рекурсии:
function countDown(num){
for(let i = num; i > 0; i —- ){
console.log(i)
}
console.log(“finished!”)
}
Здесь мы создаем цикл, который начинается с заданного числа, console.log() этого числа, а затем вычитает из него единицу. Делайте это непрерывно, пока число не станет равным 0, а затем распечатайте «finished!».
А теперь вот с рекурсией:
function countDown(num){
if(num <= 0){
console.log("Finished!")
return
}
console.log(num)
return countDown(num - 1)
}
Каждый раз, когда эта функция вызывается, мы сначала проверяем, чтобы убедиться, что передаваемое число не равно 0. Это наш базовый случай — поэтому, когда число (num) становится равным 0, мы печатаем «finished!». Затем мы ничего не возвращаем здесь, поэтому то, что сообщает функции, как только она достигает этой точки, завершено и больше не нужно запускать код. Затем мы продолжаем регистрировать число в консоли, как и раньше, но затем возвращаем эту функцию и вызываем ее с числом минус один.
Итак, допустим, что передается число 5, вот что происходит:
- Он проверяет число, видит, что это не 0 (это 5), поэтому он проходит мимо оператора if.
- Выводит 5 с помощью консоли. журнал(5)
- затем он возвращает вызов функции с числом минус 1, поэтому countDown(5–1) === countDown(4)
- Теперь он начинает сначала и проверяет, что 4 снова не равно 0.
- Затем выводит 4 с помощью console.log(4)
6. Наконец, возвращает countDown(4 –1), который равен countDown(3)
Это повторяется до тех пор, пока число не станет равным 0, а затем печатает «finished!». И это рекурсия! Поначалу это может быть немного запутанным для понимания, но после того, как вы разберете каждую часть функции, она обретет большой смысл.
Рекурсия хороша тем, что может уменьшить временную сложность, повысить ясность кода и сократить время, необходимое для написания и отладки кода. Однако иногда рекурсия плоха, потому что она может быть медленной и, возможно, использовать больше памяти. Когда использовать рекурсию, зависит от ситуации, но если основное внимание уделяется временной сложности и есть много рекурсивных вызовов, рекомендуется использовать итерацию вместо рекурсии.
Поэтому я надеюсь, что это поможет некоторым новичкам в рекурсии лучше понять, что это такое. Это популярный тип функций для написания, и он пригодится при написании алгоритмов!
