Рекурсия — это единственная идея, которую я постоянно использую, когда решаю проблемы с программированием. В большинстве случаев я не начинаю с мысли: «РЕКУРСИЯ ЭТО РЕШИТ!». Однако рекурсия просто оказывается логичным способом получить ответ. По моему профессиональному мнению, рекурсия — самая чистая форма кодирования; напишите функцию, которая будет вызывать сама себя, пока вы не получите то, что хотите! Для реализации рекурсии мы создадим вспомогательный алгоритм. 1) Identify what the smallest input is. 2) Continually break down a larger input into smaller inputs and pass those smaller inputs back into itself until you get the desired answer. 3) Define a "base case" that will stop the Recursion should the answer not be found.
Давайте сначала рассмотрим идею рекурсии. Мы пишем код, который будет выполняться до тех пор, пока мы не получим желаемый ответ или не достигнем базового случая. По сути, мы создаем петлю. Я проиллюстрирую это псевдокодом:
for (let recursion =()=›{ …answer? answer = true : false} ; answer === false; recursion())
Подобно традиционному циклу for, приведенный выше псевдокод будет продолжаться, пока выполняется второе условие; рекурсия будет продолжаться до ответа === true. В этот момент второй оператор цикла for является ложным, что завершает цикл. Выше, если answer === false, рекурсия снова вызовет себя. Это общая идея рекурсии. Вот почему создание базового варианта необходимо для предотвращения бесконечного цикла. «Ответ», который мы ищем, может отсутствовать, из-за чего рекурсия будет работать до тех пор, пока не погаснет солнце.
Давайте рассмотрим реальный пример.
Цифровой корень — это классическая алгоритмическая задача, предназначенная для проверки ваших навыков. В нем вы берете сумму всех изолированных целых чисел в числе, пока не достигнете одной единственной цифры. Например, цифровой корень из 16 равен 7. Вы выделяете «1» и «6», складываете их вместе и получаете «7». Это одна цифра и, следовательно, ответ. Рекурсия — очевидный способ добраться до цифрового корня. Давайте воспользуемся нашим вспомогательным алгоритмом:
- Наименьшим вводом будет одна цифра; это также будет нашим базовым случаем.
- Мы разобьем наш больший ввод на более мелкие входы, например. Мы начнем с «1» и «6» и сложим их вместе, получив «7». «7» — это одна цифра и, следовательно, ответ, который мы хотели. Однако, если бы наш начальный ввод был 942, мы бы разбили его на «15», которое рекурсивно передается обратно в функцию.
При написании этих задач важно понимать, что делает JavaScript. Мы написали код и знаем, что он делает, но знаем ли мы, КАК. Это кажется «понятным делом», но есть смысл звонить самому себе. Когда вы вызываете функцию в javascript, она помещается в стек выполнения. Вызовы функций накапливаются в стеке выполнения вызов за вызовом, пока мы не достигнем ответа или базового случая; JavaScript — это LIFO (последним пришел — первым ушел). В цифровом корневом регистре в функцию передается «942». Этот вызов функции помещается в стек, после чего функция вызывает сама себя, помещая digital_root(15) в верхнюю часть стека вызовов над digital_root(942). Здесь digital_root(15) совпадет с нашим базовым цифровым_root(6) и ответом из одной цифры. JavaScript вытолкнет digital_root(6) из стека выполнения, затем (15), затем (942).
Кроме того, наша функция digital_root использует итерацию с сокращением; Он перебирает каждый элемент передаваемой ему структуры данных. Важно понимать, что большинство рекурсивных функций можно реорганизовать для использования итерации, и, наоборот, большинство итерационных процессов могут использовать рекурсию. Много раз итерация была бы более производительной, если бы ввод был небольшим. Если вы хотите читать дальше, вы можете проверить стек рекурсии javascript и этот замечательный пост в блоге рекурсия против итерации. В качестве задачи вы можете использовать чистую итерацию для решения этой проблемы? Не просто пропустите это и действительно попробуйте. У Дэна Абрамова, создателя Redux, была подписка по электронной почте, которая побуждала его читателей делать домашнее задание. Я извлек из этого большую ценность, и это меня многому научило. Я призываю вас сделать это, а также. Если не я, то сделай это для Дэна Абрамова.
Продвижение вверх по рекурсии метауровня — это та самая причина, по которой люди поднялись на вершину пищевой цепи. Мы «призываем» себя до тех пор, пока не получим желаемый результат. Будь то утоление собственного голода или написание идеального алгоритма, который мы называем собой, пока мы не удовлетворены. Это еще одна причина, по которой я люблю рекурсию.
