Javascript + Программирование

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

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

Читайте нас в телеграме, там мы каждый день выкладываем полезные материалы из вселенной Front-end

Перейдем к статье

Рекурсия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Math.floor(5.5); // 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наш канал для новичков во fron-end, где мы рассказываем не только о JS

Page Visibility API

Данный интерфейс позволяет определять, когда пользователь покидает страницу. Точнее, он вызывает событие при каждом изменении состояния видимости (visibility status) страницы, например, когда пользователь сворачивает/разворачивает окно, переходит на другую вкладку и т.д.

Раньше для этого приходилось прибегать к таким уловкам, как обработка событий blur и focus. Соответствующий код выглядел так:

Приведенный код работает, но не совсем так, как ожидается. Поскольку событие blur вызывается, когда страница теряет фокус, оно может возникнуть, когда пользователь нажимает на поиск, диалоговое окно (alert), консоль или границу окна. События blur и focus сообщают нам о том, что страница активна, но не о том, видим или скрыт ее контент.

Случаи использования

Page Visibility API может использоваться для предотвращения выполнения операций, которые имеют значение, только когда пользователь видит страницу, или для выполнения фоновых операций. Еще несколько кейсов:

• если на странице отображаются данные в реальном времени, нет смысла их обновлять, если пользователь покинул страницу;

• отправка аналитических данных о действиях пользователя.

Интерфейс

Page Visibility API предоставляет 2 свойства и одно событие для получения доступа к состоянию видимости страницы:

• document.visibilityState — обновленная версия document.hidden. Возвращает 4 возможных значения:
• visible — страница видима или, если быть точнее, страница не свернута и находится в текущей вкладке;

• hidden — страница скрыта;

• prerender — начальное состояние видимой страницы: предварительный рендеринг;

• unloaded — страница выгружена из памяти;

• visibilitychange — событие объекта document, возникающее при изменении visibilityState:

Пример использования

В качестве примера рассмотрим приостановку видео и прекращение получения ресурсов из API, когда пользователь покидает страницу. Создаем шаблон проекта с помощью Vite и Yarn:

Переходим в созданную директорию, устанавливаем зависимости и запускаем сервер для разработки:

Приложение доступно по адресу http://localhost:3000.

Удаляем шаблонный код из файла main.js и добавляем элемент video в файле index.html:

Возвращаемся к main.js. Добавляем обработчик события visibilitychange объекта document:

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

Получаем ссылку на элемент video и управляем воспроизведением видео в зависимости от видимости страницы:

Прим. пер.: приведенный код работать не будет: получаем ошибку Uncaught (in promise) DOMException: play() failed because the user didn't interact with the document first.. Это объясняется тем, что вызов video.play() при изменении состояния видимости страницы на visible равносилен наличию у элемента video атрибута autoplay. Современные браузеры допускают автоматическое (без участия пользователя) воспроизведение видео только в режиме без звука. Соответственно, для того, чтобы код работал, как ожидается, элементу video необходимо добавить атрибут muted.

Когда пользователь покидает страницу, воспроизведение видео приостанавливается. Когда пользователь возвращается на страницу, воспроизведение видео продолжается.

Теперь рассмотрим пример прекращения выполнения запросов к API. Для этого напишем функцию, запрашивающую цитату из quotable.io. Добавляем в index.html элемент div для хранения цитаты:

Определяем в main.js функцию для получения произвольной цитаты с помощью Fetch API:

Приведенный код работает, но функция getQuote вызывается только один раз. Обернем ее в setInterval с интервалом в 10 секунд:

Если пользователь свернет окно или перейдет на другую вкладку, запросы все равно будут отправляться каждые 10 секунд. Давайте это исправим:

Теперь запросы будут выполняться только при условии, что страница находится в видимом состоянии.

Web Share API

Web Share API предоставляет разработчикам доступ к встроенному механизму совместного использования (native sharing mechanism) операционной системы, что особенно актуально для мобильных телефонов. Данный интерфейс позволяет делиться текстом, ссылками и файлами без создания собственного механизма или использования сторонних решений.

Случаи использования

Web Share API позволяет делиться содержимым страницы в соцсетях или копировать его в буфер обмена пользователя.

Интерфейс

Web Share API предоставляет 2 метода:

• navigator.canShare(data): принимает данные для совместного использования и возвращает логическое значение — индикатор того, можно ли этими данными поделиться;

• navigator.share(data): возвращает промис, который разрешается в случае успешного шаринга (sharing) данных. Данный метод вызывает нативный механизм и принимает данные для шаринга. Обратите внимание: этот метод может вызываться только в ответ на действие пользователя (нажатие кнопки, переход по ссылке и т.п.) (требуется кратковременная активация). data — это объект со следующими свойствами:

• url — ссылка для шаринга;

• text — текст;

• title — заголовок;

• files — массив объектов File.

Пример использования

Возьмем последний пример и добавим возможность делиться цитатой. Добавляем соответствующую кнопку в index.html:

В main.js получаем ссылку на эту кнопку и определяем функцию для шаринга данных:

Нам также потребуется глобальная переменная для хранения содержимого текущей цитаты:

Определяем обработчик нажатия кнопки:

Обратите внимание: Web Share API работает только в безопасном окружении. Это означает, что страница должна обслуживаться по протоколу https или wss.

Поддержка — 89.82%.

Broadcast Channel API

Broadcast Channel API позволяет контекстам браузера (browser contexts) обмениваться данными друг с другом. К браузерным контекстам относятся такие элементы, как окно, вкладка, iframe и т.д. По причинам безопасности контексты, обменивающиеся данными, должны принадлежать одному источнику (same origin). Один источник означает одинаковый протокол, домен и порт.

Случаи использования

Broadcast Channel API обычно используется для синхронизации окон и вкладок браузера для улучшения пользовательского опыта или повышения безопасности. Он также может применяться для уведомления одного контекста о завершении процесса в другом контексте. Другие примеры:

• отображение загруженного ресурса во всех вкладках;

• запуск сервис-воркера для выполнения фоновой задачи.

Интерфейс

Broadcast Channel API предоставляет объект BroadcastChannel, позволяющий обмениваться сообщениями с другими контекстами. Конструктор этого объекта принимает единственный аргумент: строку — идентификатор канала (channel identifier):

BroadcastChannel предоставляет 2 метода:

• broadcastChannel.close(): закрываем канал коммуникации, что позволяет браузеру выполнить сборку мусора.

При получении сообщения возникает событие message. Это событие содержит свойство data с отправленными данными, а также другие свойства, позволяющие идентифицировать отправителя, такие как origin, lastEventId, source и ports:

Пример использования

Возьмем последний пример, создадим новый контекст и добавим возможность обмена цитатами между существующим и новым контекстами.

Создаем директорию new-context в корне проекта. Создаем в ней файл index.html следующего содержания:

Создаем файл new-context/main.js.

Получаем ссылку на div и создаем новый канал коммуникации:

Добавляем обработчик события message:

Создаем канал в основном main.js и редактируем функцию getQuote:

Прим. пер.: для того, чтобы запустить данный пример локально, необходимо сделать следующее:

• в корне проекта создаем файл vite.config.js следующего содержания:

• запускаем сервер для разработки с помощью команды yarn dev;

• открываем 2 вкладки:
• по адресу http://127.0.0.1:5173/index.html;

• по адресу http://127.0.0.1:5173/new-context/index.html.

Поддержка — 92.3%.

Internationalization API

Шпаргалка по Internationalization API

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

Предположим, что мы хотим отобразить на странице "10 ноября 2022 года" как "11/10/22". Эта дата в разных странах будет выглядеть по-разному:

• 11/10/22 или ММ/ДД/ГГ в США;

• 10/11/22 в Европе и Латинской Америке;

• 22/11/10 в Японии, Китае и Канаде.

Здесь на помощь приходит Internationalization API (или I18n). Данный интерфейс позволяет решить несколько групп задач, связанных с интернационализацией и локализацией, но в этой статье мы не будем погружаться в него слишком глубоко.

Интерфейс

Для определения страны пользователя в I18n используется идентификатор локали (или просто локаль) (locale identifier, locale). Локаль — это строка, представляющая страну, регион, диалект и другие характеристики. Если точнее, локаль — это строка, состоящая из подтегов (subtags), разделенных дефисом, например:

• zh — китайский (язык);

• zh-Hant — китайский (язык), традиционные иероглифы (сценарий — script);

• zh-Hang-TW — китайский (язык), традиционные иероглифы (сценарий), используемые на Тайване (регион).

Полный список подтегов можно найти в этом RFC.

I18n предоставляет объект Intl, который, в свою очередь, предоставляет несколько специальных конструкторов для работы с чувствительными к языку данными, наиболее интересными из которых являются следующие:

• Intl.DateTimeFormat — форматирование даты и времени;

• Intl.DisplayNames — форматирование названий языков, регионов и сценариев;

• Intl.Locale — генерация и манипуляция идентификаторами локалей;

• Intl.NumberFormat — форматирование чисел;

• Intl.RelativeTimeFormat — форматирование относительного времени (завтра, 2 дня назад и т.п.).

Пример использования

В качестве примера рассмотрим использование конструктора Intl.DateTimeFormat для форматирование свойства dateAdded цитат. Данный конструктор принимает 2 аргумента: строку locale для определения правил форматирование даты и объект options для кастомизации форматирования.

Прим. пер.: в качестве первого аргумента Intl.DateTimeFormat также принимает массив локалей. Например, для установки дефолтной локали пользователя в конструктор передается пустой массив ([]).

Объект, возвращаемый Intl.DateTimeFormat, предоставляет метод format, который принимает объект Date с датой для форматирования и объект options для кастомизации отображения форматированной даты:

Обратите внимание: мы установили настройку timeZone в значение UTC для того, чтобы при форматировании даты не учитывалось локальное время пользователя.

Определяем в main.js функцию для форматирования даты:

function formatDate(dateString) {
const date = new Date(dateString);
const dateTime = new Intl.DateTimeFormat([], { timeZone: "UTC" });
return dateTime.format(date);
}

Вызываем эту функцию внутри функции getQuote для форматирования свойства dateAdded:

const getQuote = async () => {
if (document.visibilityState !== "visible") return;
try {
// ...
const parsedQuote = `<q>${content}</q> <br> <p>- ${author}</p> <br> <p>Added on ${formatDate(
dateAdded
)}</p>`;
// ...
} catch (e) {
console.error(e); 
}
};

Поддержка — 97.74%.

Прим. пер.: на днях использовал Intl.DateTimeFormat для отображения даты и времени в коротком формате:

const getDateWithHoursAndMinutes = (date) => 
new Intl.DateTimeFormat([], {
dateStyle: "short",
timeStyle: "short",
}).format(date); 
console.log(getDateWithHoursAndMinutes(new Date())); // 23.09.2022, 21:30

Надеюсь, что вы, как и я, узнали что-то новое и не зря потратили время.

Благодарю за внимание и happy coding!