Рекурсия
Алгоритмы. Красивое по звучанию слово, которое сразу заставляет вас звучать так, как будто вы знаете, что делаете. Слово, которое раньше вселяло страх (или радость) в школьников. Однако алгоритм — это просто функция, которую пишет программист. Двухстрочная функция технически является алгоритмом. Простая функция суммы — это алгоритм. Алгоритмы позволяют нам использовать все типы структур данных для выполнения действий с этими данными. По мере того, как ваша компания становится все больше и больше, а данные, с которыми вы работаете, становятся все больше и больше, эффективное использование алгоритмов в вашем коде становится все более важным для масштабируемости вашей компании. Алгоритмы позволяют вам изменить сложность Big O на более эффективную сложность.
Алгоритм — это набор рекомендаций, описывающих выполнение задачи. — Джон Вилласенор из Калифорнийского университета в Лос-Анджелесе — Ссылка
Итак, что такое рекурсия? Процесс, в котором функция прямо или косвенно вызывает саму себя, называется рекурсией, а соответствующая функция называется рекурсивной функцией. Ссылка. По сути, рекурсивная функция вызывает себя внутри функции.
Рекурсия обычно используется, в Javascript она используется, когда у вас есть объект, вложенный в другой объект.
Но что делает вышеуказанная функция? Этот алгоритм рассказал мне больше о проблеме, с которой я не был слишком хорошо знаком. Переполнение стека.
Что такое переполнение стека?
Когда вы впервые начинаете программировать, я уверен, что вы уже сталкивались с этим экраном в своей консоли.
Это защита. Вместо того, чтобы вызывать сбой браузера из-за постоянного вызова функции снова и снова, он достигает предела, при котором он автоматически останавливается.
Если мы добавим отладчик в строку над внутренним вызовом recursiveFunction, он перенесет вас в нашу консоль отладчика. Если мы затем щелкнем функцию, используя маленькую стрелку, идущую слева направо, наш стек будет увеличиваться, каждый раз добавляя новую рекурсивную функцию.
По сути, у нас заканчивается память, и стек переполняется! Таким образом, одним из недостатков рекурсии является то, что мы можем запускать что-то, что выполняется снова и снова, занимая память, поскольку мы удерживаем каждую функцию, вызываемую в стеке.
Итак, теперь, когда мы знаем, КАК работает рекурсия, она накладывает один вызов функции на другой, как вы думаете, каким будет результат этой функции?
Подождите минуту. Наш счетчик пошел к 4…. но не вернулся сделано? Почему? Именно здесь вступают в игру стеки, которые мы видели ранее в нашей консоли.
Если мы снова посмотрим на это в нашем браузере. Вы увидите, что когда мы достигнем счета 4, наше значение действительно говорит «Готово!». Однако по мере того, как мы продолжаем воспроизводить рекурсивную функцию, она начинает выскакивать из вершины стека.
Почему это? Что ж, если мы разберем наш стек, он будет выглядеть вот так.
Итак, мы можем просто исправить это, используя технику всплывающего окна, просто добавив один дополнительный возврат.
Это подводит нас к трем законам рекурсии, сформулированным Runestone:
- Рекурсивный алгоритм должен иметь базовый случай. (Наш оператор if).
- Рекурсивный алгоритм должен изменить свое состояние и перейти к базовому случаю. (2 возврата движутся к возврату «Готово!»)
- Рекурсивный алгоритм должен вызывать сам себя рекурсивно. (Вызов функции внутри себя).
Хорошо, давайте поместим наше обучение в общий вопрос. Является ли это слово палиндромом? (Читается то же самое задом наперёд, например, гоночный автомобиль).
Итак, что мы делаем здесь, так это устанавливаем нашу базу, то есть если наша длина слова равна 0 или 1 (потому что это зависит от того, четная или нечетная длина слова). Если это так, значит, мы достигли нашей базы, и слово должно быть палиндромом.
Однако, если мы еще не достигли длины 0 или 1, мы переходим к нашему второму закону изменения состояния. Если первый элемент равен нашему последнему элементу, то они совпадают! Это означает, что мы можем снова вернуть нашу функцию, но на этот раз мы вырезаем первую и последнюю буквы (потому что мы только что подтвердили, что они одинаковы). Затем он возвращается к началу, чтобы проверить нашу базовую функцию if.
Однако если бы мы ввели isPalindrome(‘dog’), функция увидела бы, что первый и последний элементы не совпадают, и поэтому вернула бы false!
Это отличное использование рекурсивной функции!
