Алгоритмы для веб-разработчиков простыми словами (часть 3)

Здравствуйте, друзья!

Мы продолжаем разбирать максимально простым языком алгоритмы и структуры данных на JavaScript. Тема нашей сегодняшней статьи — рекурсия. Для многих разработчиков рекурсия кажется чем-то очень сложным и непонятным, но не переживайте, не так страшен черт, как его малюют.

И сегодня мы узнаем, как устроена рекурсия, а также разберем алгоритм сортировки массива под названием Quick Sort или, как еще его называют, быстрая сортировка Хоара. Как вы уже догадались, этот алгоритм рекурсивный.

Если вы еще не читали нашу первую статью (про алгоритмы поиска и Big O нотацию), то можете найти ее здесь.

Ссылку на вторую статью (про алгоритмы сортировки и оценку сложности алгоритмов по скорости и памяти) вы можете найти здесь.

А сейчас давайте перейдем к теме статьи.

Рекурсия

Рекурсия, если максимально упростить, это вызов функцией самой себя. Этот приём программирования можно использовать, когда есть возможность разбить задачу на несколько более простых подзадач. И, написав решение этой подзадачи в функции и вызывая такую функцию рекурсивно, мы можем все эти подзадачи итеративно решить.

Давайте взглянем на простой пример.

У нас есть простая функция обратного отсчёта:

function countDown(n) {

  for (let i = n; i > 0; i--) {

    console.log(i);

  }

  console.log('Финиш');

}

Данная функция принимает аргументом число n и выводит на экран числовую последовательность от n до 1 включительно, а в конце, после завершения работы цикла, выводит на экран слово «Финиш».

Давайте вызовем эту функцию, передав в нее число 3. В консоли мы получим следующий результат: «3 2 1 Финиш».

countDown(3); // 3 2 1 Финиш

Теперь перепишем эту функцию на рекурсивный манер:

function countDownRecursive(n) {

  if (n <= 0) {

    console.log('Финиш');

    return;

  }

  console.log(n);

  countDownRecursive(n - 1);

}

Разберемся, как эта функция работает. Первым делом, чтобы не получить бесконечный цикл вызовов функции и как результат ошибку «stack overflow», которая говорит нам о превышении лимита вызовов для функции в стеке, нужно определить так называемый базовый случай.

Базовый случай — это условие, при котором наша функция должна перестать вызывать саму себя рекурсивно.

Так как наш цикл работал до тех пор, пока i > 0, то здесь условие для прерывания цикла должно быть следующим:

if (n <= 0) {

  console.log('Финиш');

  return;

}

То есть, как только n будет меньше или равно нулю, мы перестаем рекурсивно вызывать функцию и выходим из нее. Перед выполнением оператора return необходимо будет вызвать наш console.log('Финиш'), потому что именно это действие и будет последним в работе функции.

По сути, базовый случай работает как оператор break в циклах, то есть прерывает вызов функцией самой себя, чтобы мы могли вернуть результат ее выполнения.

function countDownRecursive(n) {

  if (n <= 0) {

    console.log('Финиш');

    return;

  }

  console.log(n); // Выводим в консоль n

  countDownRecursive(n - 1);
}

Дальше мы выводим в консоль текущее значение числа n. И, следующим шагом, снова вызываем нашу функцию countDownRecursive() и передаем в нее n - 1.

Как вы помните, в примере с циклом for, на каждой итерации цикла мы уменьшали число i на единицу (i--), поэтому здесь, по аналогии, передаем n - 1.

Запустим функцию и получим в консоли следующий результат:

countDownRecursive(3); // 3 2 1 Финиш

Результат, как вы видите, аналогичен результату работы простой функции countDown.

Давайте теперь чуть подробнее разберём, как работает рекурсивная функция.

Как работает рекурсивная функция

function countDownRecursive(n) {

  if (n <= 0) {

    console.log('Финиш');

    return;

  }

  console.log(n);

  countDownRecursive(n - 1);

}

countDownRecursive(3); // 3 2 1 Финиш

Итак, сначала мы вызываем функцию countDownRecursive со значением 3.

countDownRecursive(3);

Базовый случай не отрабатывает, потому что n > 0. Мы выводим число 3 в консоль и дальше снова вызываем функцию, передав в нее n - 1, то есть 3 - 1 или просто число 2.

countDownRecursive(3);

  countDownRecursive(2);

Повторяем эту процедуру, пока не дойдем до нуля:

countDownRecursive(3);

  countDownRecursive(2);

    countDownRecursive(1);

      countDownRecursive(0); // Отрабатывает базовый случай!

И вот здесь уже срабатывает базовый случай. Так как 0 === 0, выводим в консоль слово «Финиш» и дальше срабатывает оператор return.

countDownRecursive(3);

  countDownRecursive(2);

    countDownRecursive(1);

      countDownRecursive(0); // Отрабатывает базовый случай!

      return;

    return;

  return;

return;

Дальше происходит завершение работы всех предыдущих функций (потому что неявно завершенная функция возвращает undefined, то есть как только выполнение нашей функции доходит до закрывающей фигурной скобки, происходит return undefined).

Здесь вы можете подумать, что это всё очень сложно, и почему бы не использовать такой понятный и простой цикл for?

Важно отметить, что, действительно, не везде нужно применять рекурсию. Но бывают задачи, где рекурсивное решение выглядет очень элегантно и занимает гораздо меньше строчек кода, чем с использованием традиционных циклов.

Давайте разберем один из таких примеров.

Числа Фибоначчи

Как вы знаете, ряд Фибоначчи — это числовая последовательность, первые два числа которой являются единицами, а каждое последующее за ними число является суммой двух предыдущих.

Автором данной числовой последовательности был Леонардо Пизанский (более известный под прозвищем Фибоначчи) из итальянского города Пизы — один из крупнейших математиков средневековой Европы.

Вот так ряд Фибоначчи выглядит на практике:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181 //...и так далее до бесконечности.

Иногда перед первой единицей добавляют еще и ноль, но мы не будем рассматривать данный случай, а рассмотрим классический ряд Фибоначчи, как в средневековых книгах (но только без кроликов).

Наша задача — написать функцию, которой можно передать номер элемента ряда Фибоначчи, и на выходе из функции получить значение этого элемента.

Допустим, мы ищем 10-ый элемент в последовательности. Значением этого элемента будет 55. Для 12-го элемента значением будет 144 и так далее.

Вот так будет выглядеть эта функция, написанная с применением рекурсии:

const fibonachi = (n) => {

  if (n < 2) {

    return n;

  }

  return fibonachi(n - 1) + fibonachi(n - 2);

};

console.log(fibonachi(6)); // 8

В результате работы функции в консоли мы получим число 8. Можете это проверить: если вы посмотрите на ряд Фибоначчи выше, то увидите, что значением 6-го элемента в ряду будет число 8.

Давайте разберём, как работает данная функция.

const fibonachi = (n) => {

  // Реализация функции

};

Объявляем стрелочную функцию fibonachi, которая принимает аргументом число искомого элемента в ряду — n.

const fibonachi = (n) => {

  if (n < 2) {

    return n;

  }

};

Далее определяем базовый случай, т.е. условие, при котором выходим из рекурсии.

Так как мы будем последовательно уменьшать число n (об этом ниже), то нет смысла делать это бесконечно.

Как только n оказывается меньше 2, то это значит, что мы достигли начала ряда Фибоначчи, а значит дальше нам двигаться не нужно и можно возвращать n обратно вызывающему коду.

const fibonachi = (n) => {

  if (n < 2) {

    return n;

  }

  return fibonachi(n - 1) + fibonachi(n - 2);

};

console.log(fibonachi(6)); // 8

Если же базовый случай не отработал, то снова вызываем функцию, передав в ее аргументы n - 1 и n - 2 соответственно, и складываем результат этих функций между собой по следующей формуле: F(n) = F(n - 1) + F(n - 2). Эта формула позволяет нам найти число из ряда Фибоначчи. Так как каждое число равно сумме двух предыдущих чисел в цепочке, то именно эту формулу мы реализовали в нашей функции.

Если вам до конца не понятно объяснение данного алгоритма, то, во-первых, это абсолютно нормально, а во-вторых, можете посмотреть подробное видео, объясняющее работу данной функции здесь.

Быстрая сортировка Хоара

А теперь рассмотрим более сложный алгоритм. Он называется быстрая сортировка (Quick Sort) или сортировка Хоара.

Данный алгоритм был разработан английским информатиком Тони Хоаром во время работы в МГУ в 1960 году.

И вот здесь как раз будет применяться рекурсия.

Как вы помните, в предыдущей статье мы с вами разбирали широко известный в узких кругах алгоритм — пузырьковую сортировку. Ее единственный недостаток — это крайне низкая эффективность. Быстрая же сортировка является улучшенной версией подобных алгоритмов сортировки с помощью прямого обмена.

Итак, в чем суть. Имеется неотсортированный массив чисел arr.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

Наша задача написать функцию, которая будет принимать в себя аргументом этот массив и возвращать его полностью отсортированным по возрастанию.

Быстрая сортировка относится к алгоритмам из серии «разделяй и властвуй».

Небольшое отступление. Алгоритмы типа «разделяй и властвуй» (англ. divide and conquer) — это парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.

Наш алгоритм будет сводиться к следующим шагам:

1. Выбираем элемент из массива и считаем его опорным (в англоязычной литературе его называют pivot).

2. Сортируем элементы в массиве таким образом, чтобы элементы меньше опорного размещались в подмассиве перед ним, а большие или равные — в подмассиве после.

3. Рекурсивно применяем первые два шага к двум подмассивам слева и справа от опорного элемента. Т.е. дробим наш массив на подмассивы и сортируем их относительно опорного элемента, пока в этих подмассивах не останется по одному элементу или меньше. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы. Это как раз и будет базовым условием, при котором мы прервем рекурсию.

Вот здесь вы можете увидеть визуализацию работы быстрой сортировки (а также многих других алгоритмов).

А вот так выглядит реализация сортировки Хоара на JavaScript:

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  let pivotIndex = Math.floor(arr.length / 2);

  let pivot = arr[pivotIndex];

  let less = [];

  let greater = [];

  for (let i = 0; i < arr.length; i++) {

    if (i === pivotIndex) continue;

    if (arr[i] < pivot) {

      less.push(arr[i]);

    } else {

      greater.push(arr[i]);

    }

  }

  return [...quickSort(less), pivot, ...quickSort(greater)];

}

console.log(quickSort(arr));

Подробный разбор алгоритма сортировки Хоара

Давайте подробно разберём, как работает данная сортировка.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  // Реализация алгоритма

}

Создаем функцию quickSort() и передаем аргументом неотсортированный массив.

Дальше, как вы помните, необходимо определить базовый случай выхода из рекурсии.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  // Базовый случай выхода из рекурсии

  if (arr.length <= 1) {

    return arr;

  }

}

Так как нам предстоит дробить основной массив на подмассивы и сортировать элементы в этих подмассивах относительно опорного элемента (об этом ниже), то как только такие подмассивы будут содержать по одному элементу или будут пустыми, нам нет смысла дальше продолжать разбивать их на более мелкие части, поэтому здесь мы выйдем из рекурсии.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  // Индекс опорного элемента в массиве

  let pivotIndex = Math.floor(arr.length / 2);

  // Опорный элемент

  let pivot = arr[pivotIndex];

}

Теперь определим индекс в массиве так называемого опорного элемента. Для этого создадим переменную pivotIndex, передадим в функцию Math.floor длину массива, поделим результат на 2 и получившееся число присвоим переменной pivotIndex. Функция Math.floor, как вы знаете, округляет результат в меньшую сторону:

Math.floor(5.5); // 5

Затем определим сам опорный элемент. Для этого кладем в переменную pivot значение массива по индексу pivotIndex. В массиве arr значением pivotIndex будет 5 (длина массива — 11. 11 делим на 2 и округляем в меньшую сторону, получаем 5). Значением pivot будет -12.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  let pivotIndex = Math.floor(arr.length / 2);

  let pivot = arr[pivotIndex];

  // Сюда положим все элементы меньше опорного

  let less = [];

  // Сюда положим все элементы больше опорного

  let greater = [];

}

Дальше нужно объявить два пустых подмассива less и greater. В массив less будем сохранять все элементы, которые меньше опорного, а в greater все элементы, которые больше опорного.

Дальше в цикле for мы пробегаем по всем элементам массива и сравниваем каждый элемент с опорным.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  let pivotIndex = Math.floor(arr.length / 2);

  let pivot = arr[pivotIndex];

  let less = [];

  let greater = [];

  for (let i = 0; i < arr.length; i++) {

    // Пропускаем итерацию, если индекс текущей итерации совпадает
    // с индексом опорного элемента

    if (i === pivotIndex) continue;

    // Если опорный элемент больше элемента в массиве, добавляем 
    // этот элемент в массив less

    if (arr[i] < pivot) {

      less.push(arr[i]);

      // Иначе добавляем его в массив greater

    } else {

      greater.push(arr[i]);

    }

  }

}

Затем у нас идут три условия. В первом условии мы сравниваем индекс текущей итерации цикла с индексом опорного элемента в массиве.

Если они совпадают, то текущую итерацию цикла мы завершаем с помощью ключевого слова continue, так как нам не нужно добавлять опорный элемент в один из наших подмассивов.

Далее во втором условии мы сравниваем элемент массива с опорным элементом. Если опорный элемент больше, то добавляем наш текущий элемент массива в массив less.

В противном же случае, добавляем текущий элемент массива в массив greater (третье условие).

В итоге, после завершения цикла for, у нас на выходе будет 2 массива: less с числами меньше опорного и greater с числами больше опорного или равными ему.

И дальше мы возвращаем массив, в который разворачиваем результат рекурсивного выполнения функции, принимающей в качестве аргумента массив less. Дальше вставляем наш опорный элемент pivot, а после снова разворачиваем результат выполнения функции для массива greater.

const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];

function quickSort(arr) {

  if (arr.length <= 1) {

    return arr;

  }

  let pivotIndex = Math.floor(arr.length / 2);

  let pivot = arr[pivotIndex];

  let less = [];

  let greater = [];

  for (let i = 0; i < arr.length; i++) {

    if (i === pivotIndex) continue;

    if (arr[i] < pivot) {

      less.push(arr[i]);

    } else {

      greater.push(arr[i]);

    }

  }

  // Рекурсивно вызываем функцию quickSort, передаем туда наши
  // массивы и разворачиваем результат в возвращаемый массив,
  // не забывая вставлять посередине опорный элемент

  return [...quickSort(less), pivot, ...quickSort(greater)];

}

// Выводим в логи результат работы функции

console.log(quickSort(arr));

Когда функция доходит до базового случая, рекурсивный вызов функции заканчивается и все одиночные массивы соединяются в один большой отсортированный массив.

Выведем в консоль результат работы функции и убедимся в этом.

Быстрая сортировка в среднем и лучшем случае выполняется за Θ(n * log(n)) и Ω(n * log(n)) соответственно.

В худшем случае время выполнения алгоритма занимает О(n^2).

Более подробно про лучшее, среднее и худшее время выполнения алгоритма быстрой сортировки можно прочитать здесь.

На этом мы закончили третью статью из нашего цикла статей по алгоритмам. Спасибо за внимание и до новых встреч!