Этот пост пытается прояснить идею рекурсии с использованием алгоритма, который почти не требует рекурсивной реализации: двоичного поиска. Прежде чем перейти к реализации JavaScript, давайте рассмотрим, как работает двоичный поиск.
Представьте, что у нас есть список имен, отсортированных по алфавиту.
Мы хотим выяснить две вещи:
- Есть ли в списке имя «Брайан»?
- Если да, то где это имя находится в списке?
Один из способов сделать это программно - проверять каждое имя в нашем списке, пока мы не найдем имя или не дойдем до конца списка. Однако, поскольку наш список имен отсортирован, бинарный поиск позволит достичь наших целей намного быстрее.
Бинарный поиск работает путем сравнения имени, которое мы хотим найти («Брайан»), с именем в середине списка («Дарси»). Поскольку «Дарси» идет в алфавите после «Брайана», то мы знаем, что «Брайан» не может стоять после «Дарси» в нашем списке.
Затем мы повторяем процесс (psst: recursion), используя только первую половину нашего списка. В нашем списке теперь четыре имени, поэтому, в зависимости от кода, серединой списка может быть «Бетси» или «Брайан». Предположим, что наш код угадывает отчество «Бетси».
«Бетси» идет раньше «Брайана», а мы устраняем и «Бетси», и «Алана». При третьем предположении наш двоичный поиск угадает «Брайан» и завершит поиск.
Если бы имя не было в списке, наш двоичный поиск сократил бы список до одного имени, прежде чем определил бы, что имя не может быть найдено.
Реализация Javascript
Давайте посмотрим на этот алгоритм в виде функции JavaScript:
var binarySearch = function(array, target, min, max) {
if (min === undefined) min = 0;
if (max === undefined) max = array.length - 1;
var guess = Math.floor(((max - min) / 2) + min);
if (max <= min && array[guess] !== target) return null;
else if (array[guess] === target) return guess;
else if (array[guess] < target) return binarySearch(array, target, guess + 1, max);
else return binarySearch(array, target, min, guess - 1);
};
Это рекурсивная функция, что означает, что она вызывает сама себя. Но прежде чем мы перейдем к рекурсивным аспектам функции, давайте начнем с самого начала.
Параметр array - это наш список имен, а target - это имя, которое мы ищем. Параметры min и max определяют раздел списка, который мы исследуем. Эти разделы становятся меньше по мере того, как мы удаляем части из нашего списка.
В первой строке функции мы копируем массив, чтобы не изменять оригинал. Затем мы проверяем, были ли переданы аргументы для min и max. Если аргументы не были переданы, мы устанавливаем min равным 0 (начало массива) и max равным array.length-1 (конец массива).
Затем программа назначает guess как медианное значение допустимой части массива. Другими словами, guess - это индекс. При первом вызове binarySearch, guess будет медианным всего массива. Если длина массива равна 9, тогда guess будет (9–0) / 2 + 0, который затем округляется с помощью Math.floor (), давая значение 4. Если длина равна 8, тогда guess будет (8–0) / 2 + 0, снова 4. Таким образом, в отличие от примера выше, этот код будет округлять в меньшую сторону, если длина даже.
Затем функция сравнивает имя по индексу guess с целевым. Если массив был сужен до одного имени и это имя не является целевым, binarySearch вернет null. Если имя в guess совпадает с именем цели, binarySearch возвращает guess, индекс, по которому имя находится в массиве.
В противном случае, если имя, расположенное в guess, стоит перед целью в алфавите, мы снова вызываем binarySearch для сокращенной части массива. Это центральная идея рекурсии; вместо того, чтобы создавать цикл для второй половины функции, мы можем просто вызвать функцию снова с другим набором аргументов. В приведенном здесь примере вызов нашей новой функции установит min на одно место после guess. Это работает и в другом направлении; если имя в guess меньше целевого, тогда новое max становится на единицу меньше, чем guess.
Вывод
Двоичный поиск - отличный пример того, как алгоритм выглядит элегантно, если реализован рекурсивно. Однако имейте в виду, что рекурсия более затратна, чем цикл с точки зрения производительности.
Этот пост был вдохновлен следующим репозиторием GitHub, который я настоятельно рекомендую, если вы хотите попрактиковаться в рекурсии: https://github.com/JS-Challenges/recursion-prompts
