Рекурсия — очень популярный вопрос, используемый для тестирования инженеров-программистов. Тот факт, что это не является повседневным делом на большинстве должностей инженеров-программистов, не имеет значения.
Интервьюеры любят спрашивать о решениях, которые требуют рекурсии. Итак, если вы можете справиться с ответом, это показывает, что вы понимаете важную концепцию кодирования. Мы рассмотрим основы использования JavaScript.
Определение первое, из всегда надежной Википедии:
Рекурсия — это метод решения проблемы, при котором решение зависит от решений более мелких экземпляров той же проблемы. Такие проблемы обычно могут быть решены путем итерации, но для этого необходимо идентифицировать и индексировать меньшие экземпляры во время программирования.
Хм… не уверен, что это действительно отражает то, что мы делаем.
Второе определение от меня:
Функция, которая вызывает сама себя и которая имеет условие, которое не позволяет ей вызывать себя бесконечно.
Ну вот, немного о начале работы! И что очень важно, у него есть условие остановки, также известное как «базовый случай».
Базовый случай — это то, что нужно функции, чтобы прекратить выполнение. Без него вы будете вызывать функцию снова и снова, вплоть до бесконечности. Стек вызовов будет превышен, после чего обычно компьютер зависает. Грусть и поражение. Мы можем этого избежать.
Зачем вообще рекурсия?
Рекурсия отлично подходит для задач, которые можно разбить на куски размером с укус. Это хорошая концепция для оттачивания всей разработки программного обеспечения. Разбивка проблемы на более мелкие части — лучший способ разобраться со сложной проблемой.
На мой взгляд, именно по этой причине рекурсия так часто встречается в вопросах на собеседовании по программированию.
Они ищут вашу способность разобрать проблему, проанализировать ее и найти решение. Самое главное, понимаете ли вы конечную цель? Можете ли вы кодировать так, чтобы всегда иметь в виду конечную цель?
Мы можем сделать это с помощью итерации, но это может занять целую вечность. Можете ли вы придумать способ «меньше строк кода» сделать это? Все это «почему» рекурсии.
Если вам не нравится вся эта абстракция, попробуйте рассматривать ее как вызов. Вы можете сделать это!
(Вы вроде должны, так что давайте наслаждаться!)
Итак, небольшое напоминание: что мы делаем без рекурсии? Ответ - итерация.
Итерация иногда рассматривается как «наивная». Для JavaScript подумайте о различных циклах:
- для в цикле
- для цикла let
- пока цикл
Также итерационные методы массива, такие как:
- для каждого()
- уменьшать()
- карта()
- фильтр()
Этим итеративным методам массива часто требуется дополнительная функция обратного вызова.
Итак, давайте начнем. Первый способ увидеть рекурсию в действии — это старая добрая функция обратного отсчета. Опять же, мы могли бы повторить, но давайте бросим себе вызов!
Рекурсивный обратный отсчет
Задача:создайте функцию с использованием JavaScript, которая принимает число в качестве параметра и ведет обратный отсчет от этого числа до нуля.
Код:
На что следует обратить внимание:
- Линия 2 чрезвычайно важна. Это ваш базовый случай. Это то, что остановит вызов функции в бесконечность (и зависание вашего браузера).
- Прежде чем вы даже наберете букву для этой проблемы, вам нужно придумать «Как ваш код выходит из функции?»
- Другой способ взглянуть на это так: «Когда он должен перестать работать?» Нам всем нужна конечная цель, особенно для ваших маленьких функций. Они будут продолжаться до тех пор, пока ваш стек вызовов не будет исчерпан и ваш компьютер не станет грустным, разочарованным, возможно, сломанным.
- Там еще логику вставить, после базового случая. У нас все еще есть решение, чтобы войти или найти.
- Как получить свое решение? Функция вызывает себя внутри блока кода той же функции.
- Шестая строка — вторая по важности. Нужно изменить параметр, потому что после одного прогона рекурсии мы уже не на том же месте. Обновите свой код (параметр).
- Нам нужно перейти к следующему числу, поэтому здесь мы меняем вторую переменную с начального значения (10 секунд) на (9 секунд).
Слишком долго, что мне делать?
- У вас есть базовый вариант, также известный как условие выхода для вашей функции.
- Вы вызываете функцию внутри указанной функции И увеличиваете параметр, который передается в ту же функцию.
- Вы имеете в виду свою цель, направление, которому нужно следовать, и возможность выйти и увеличить свой путь по тому же пути.
Великолепно! Вы понимаете?
Если честно, если вы тут задаетесь вопросом: «Окей, круто. Я действительно не понимаю этого, но я просто продолжу читать…”
Останавливаться.
По моему скромному мнению, рекурсивная функция обратного отсчета — лучший пример. Если вы сейчас запутались, не идите дальше. Найдите что-нибудь другое, что вы делаете для решения этой конкретной проблемы.
Вы всегда будете помнить тот момент, когда у вас «получилось» решить эту рекурсивную задачу. Если этот момент не сейчас, не путайте себя еще больше. Возвращайтесь, когда у вас будет момент «ага».
Итак,… зловещие предупреждения в сторону, что еще мы можем повторить?!
Фракталы!
Я знаю, что это за чертовщина?
Никогда не слышал об этом до рекурсии. И если я это сделал, то до сих пор я успешно избегал необходимости в них. Ну, мы здесь, чтобы бросить вызов, так что давайте сделаем это!
Рекурсивные фракталы
Итак, новая порция математики на подходе!
Согласно Google, фракталы это:
«Кривая или геометрическая фигура, каждая часть которой имеет такой же статистический характер, как и целое».
Полезным изображением является:
Ну, мне это не помогло. И, конечно же, я думал, что я визуал. Кроме того, что это за чертовщина: 5!
Мне показалось, что мы громко кричали «ПЯТЬ», но через код.
«5! ” — это просто способ сказать кодом: 5 х 4 х 3 х 2 х 1 = 120.
Точно так же «8! будет: 8 х 7 х 6 х 5 х 4 х 3 х 2 х 1 = 40 320.
Ух, какой прыжок. Давайте повеселимся с (маленькими) факториалами.
Для упрощения базовый факториал — это просто число (или параметр), которое увеличивается вниз и умножается на следующее число, меньшее, чем указанный параметр.
Задача:Используя JavaScript и рекурсию, найдите ответ на 5!
Код:
На что следует обратить внимание:
- Опять же, мы устанавливаем базовый случай в строке 3. Именно здесь факториальная функция знает, что нужно прекратить проверку параметра и просто дать нам результат. Больше никакой рекурсии после этого условия.
- Также снова мы увеличиваем параметр, переданный функции. (строка 11). Нам нужно уменьшить это, чтобы мы могли убедиться, что базовый случай в конечном итоге будет достигнут.
- Мы вызываем функцию внутри той же функции. Хорошая рекурсия, посмотри, как ты идешь!
Слишком долго, что мне делать?
- Базовый случай для факториала, когда мы получаем ноль, мы возвращаем 1. Почему? Магия математики! Но на самом деле факториал числа в математике — это произведение всех положительных чисел, меньших или равных числу. Но нет положительных значений меньше нуля, поэтому нам нужно остановиться на 0, следовательно, 0! равно 1.
- Поверь мне, если это звучит выдуманно, я с тобой в этом. Но я думаю, что это описание было довольно хорошим и простым: видео.
- Для факториала мы все еще увеличиваем параметр. Начните с 5, вызовите функцию, но двигайтесь к цели. Мы не можем идти вверх: 5, 6, 7, 8, и так далее. Это не то, что пытается найти факториал.
- Мы уменьшаем параметр с пяти до четырех. И при этом мы выполняем функцию, которая представляет собой «текущий параметр», умноженный на «текущий параметр» минус 1.
- Здесь это должно быть умножение 5 x 4. Мы сохраняем этот результат/ответ и продолжаем работать над ним. Мы вызываем функцию, пока не достигнем базового случая/условия выхода.
Разве это не красиво? Что ж, многие запутанные вещи на самом деле прекрасны.
Заключение
Я чувствовал себя очень хорошо, когда я понял это изначально. Это было частью долгого пути к тому, чтобы почувствовать себя более компетентным в программировании в целом.
По сути, рекурсия может отлично подойти для решения определенных проблем. В основном это может быть хорошим примером вашей способности обдумать проблему, разбить ее на более мелкие части и найти хорошо продуманное решение.
Увидеть большую картину. Думай иначе. Вставьте сюда модную фразу.
Я надеюсь, что это было хорошо для тех из вас, кто был напуган этой концепцией. И я надеюсь, вы увидели красоту в кодировании задач рекурсии JavaScript. Наконец, мне понравились эти ресурсы, и вы, возможно, тоже:
