Мощь рекурсии в JavaScript

Доброго времени суток, друзья!

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

Простым примером рекурсии является вычисление факториала натурального числа:

function factorial(n) {   return (n != 1) ? n * factorial(n - 1) : 1; } 

Специально для визуалов:

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

Преимущества рекурсии

Преимуществами рекурсии является следующее:

1. Меньше кода.
2. Код выглядит чище.
3. Меньше времени на написание кода и устранение ошибок.
4. Меньше времени на запуск алгоритма (временная сложность алгоритма).
5. Легче решать задачи при работе с древовидными структурами данных.
6. Легче визуализировать алгоритмы.

Недостатки рекурсии

К недостаткам рекурсии можно отнести следующее:

1. Может быть медленной.
2. Может привести к переполнению стека вызовов.
3. Потребляет больший объем памяти, чем цикл (если не используется оптимизация хвостовой рекурсии).

Зачем нам рекурсия?

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

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

Примеры

Лучший способ понять рекурсию — рассмотреть парочку примеров.

Перебор объектов (проход по объектам, траверс объектов)

Как упоминалось ранее, рекурсия облегчает работу с древовидными структурами данных. Глубоко вложенных объект — это, по сути, древовидная структура данных.

Представим, что у нас имеется некий объект, представляющий элемент HTML DOM. Данный элемент имеет вложенные объекты. Каждый вложенный объект также может иметь дочерние элементы. Другими словами, каждый «ребенок» является элементом HTML DOM и может иметь «детей», так что в зависимости от количества потомков это может быть по-настоящему большой объект.

Наша задача — получить все объекты, независимо от «вложенности».

Мы будем искать свойство «style» (представленное атрибутами элемента) и менять значения свойств «border», «textColor» и «width» так, чтобы их можно было использовать в JavaScript.

Вот пример стилей объекта, которые необходимо изменить:

{     "border": {         "color": "hotpink",         "width": "2px"     },     "textColor": "paleviolet",     "width": "0.45" } 

Для изменения цвета текста в HTML используется свойство «color», поэтому textColor должно быть преобразовано в color.

Допустим, что значение width — это проценты от области просмотра клиента (должно быть преобразовано в 45vw), а border должно быть преобразовано в { borderColor: ‘hotpink’, borderWidth: ‘2px’ }.

Наш «древовидный» объект выглядит так:

{     "type": "div",     "style": {},     "children": [{         "type": "div",         "style": {             "backgroundColor": "black",             "border": {                 "color": "hotpink",                 "width": "2px",                 "style": "dashed"             },             "fontStyle": "italic",             "padding": "20px 25px",             "textColor": "white"         },         "children": [{                 "type": "button",                 "style": {                     "backgroundColor": "#fda512",                     "border": {                         "color": "red"                     },                     "textColor": "#fff"                 }             },             {                 "type": "label",                 "style": {                     "height": "0.04",                     "width": "0.04"                 },                 "children": [{                     "type": "label",                     "style": {                         "border": {                             "style": "solid",                             "width": "5px"                         },                         "fontStyle": "italic"                     },                     "children": [{                         "type": "span",                         "style": {                             "backgroundColor": "#039392",                             "borderRadius": "10px",                             "height": "0.03",                             "outline": "none",                             "width": "0.783"                         }                     }]                 }]             }         ]     }] } 

Итак, мы имеем древовидную структуру данных, где каждый вложенный объект начинается со свойства «children».

Создадим функцию «transformStyleObject», принимающую стили объекта и исправляющую их — возвращающую новый объект, который можно использовать в JS и DOM:

function transformStyleObject(styleObj) {     const result = {}     const keys = Object.keys(styleObj)      keys.forEach(key => {         if (key === 'border') {             const {                 color,                 width,                 style             } = styleObj.border             if (color) result.borderColor = color             if (width) result.borderWidth = width             if (style) result.borderStyle = style         } else if (key === 'textColor') {             result['color'] = styleObj.textColor         } else if (key === 'width') {             result['width'] = `${Number(styleObj.width) * 100}vw`         } else if (key === 'height') {             result['height'] = `${Number(styleObj.height) * 100}vh`         } else {             result[key] = styleObj[key]         }     })     return result }  const result = transformStyleObject({     border: {         width: '2px',         style: 'dashed',     },     height: '0.42', })  console.log(result) // result: { borderWidth: '2px', borderStyle: 'dashed', height: '42vh'} 

Для прохода по объекту мы можем использовать стандартный цикл:

function transformAll({     type = '',     style = {},     children = [] }) {     const result = {         type,         style: transformStyleObject(style),         children     }      if (Array.isArray(result.children)) {         for (let i = 0; i < result.children.length; i++) {             const child = result.children[i]             child.style = transformStyleObject(child.style)              if (Array.isArray(child.children)) {                 for (let i = 0; i < child.children.length; i++) {                     const childsChild = child.children[i]                     childsChild.style = transformStyleObject(childsChild.style)                      if (Array.isArray(childsChildren.children)) {                         for (let i = 0; i < childsChildren.children.length; i++) {                             const childsChildsChild = childsChild.children[i]                             // и т.д.                         }                     }                 }             }         }     }     return result } 

Недостатки такого подхода очевидны и состоят в следующем:

1. Код становится длинным
2. Его становится трудно читать и поддерживать
3. Он становится чувствительным к изменениям
4. Его труднее тестировать
5. Может возникнуть путаница с переменными

Используем рекурсию для решения этих проблем:

function transformAll({     type = '',     style = {},     children = [] }) {     const result = {         type,         style: transformStyleObject(style),         children     }     if (Array.isArray(result.children)) {         result.children = result.children.map(transformAll)     }     return result } 

Результат выглядит так:

{     "type": "div",     "style": {},     "children": [{         "type": "div",         "style": {             "backgroundColor": "black",             "borderColor": "hotpink",             "borderWidth": "2px",             "borderStyle": "dashed",             "fontStyle": "italic",             "padding": "20px 25px",             "color": "white"         },         "children": [{                 "type": "button",                 "style": {                     "backgroundColor": "#fda512",                     "borderColor": "red",                     "color": "#ffffff"                 },                 "children": []             },             {                 "type": "label",                 "style": {                     "height": "4vh",                     "width": "4vw"                 },                 "children": [{                     "type": "label",                     "style": {                         "borderWidth": "5px",                         "borderStyle": "solid",                         "fontStyle": "italic"                     },                     "children": [{                         "type": "span",                         "style": {                             "backgroundColor": "#039392",                             "borderRadius": "10px",                             "height": "3vh",                             "outline": "none",                             "width": "78.3vw"                         },                         "children": []                     }]                 }]             }         ]     }] } 

Согласитесь, теперь код выглядит гораздо лучше! Вот как работает эта рекурсия:

1. transformAll принимает объект, представляющий HTML DOM элемент
2. Преобразует стили элемента
3. Проверяет, имеются ли вложенные элементы по свойству «children»
4. Если вложенные элементы имеются, функция «transformStyleObject» вызывается для каждого из них
5. Рекурсия позволяет обработать каждый объект, независимо от уровня его вложенности

Работаем с файлами и папками

Лично я люблю писать функциональный код. И рекурсия отлично для этого подходит.

Напишем программу, которая будет проверять каждую директорию с именем "__test__" и определять, какие из модульных тестов не были использованы (по окончанию имени на ".test.js").

Каждая папка будет «модулем». Если в ней отсутствует директория с именем "__test__" или файл, имя которого заканчивается на ".test.js", значит, он не содержит тестов.

При обнаружении теста будет возвращаться объект, содержащий информацию о директории, например:

{     "../javascript-algorithms/src/algorithms/math/linked-list": {         "name": "linked-list",         "category": "algorithms",         "subcategory": "math",         "totalFiles": 0,         "filesList": []     } } 

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

Для этого отлично подойдет рекурсия.

Для примера возьмем этот репозиторий с JS-алгоритмами. Скачиваем его. Заходим в папку «src» и удаляем из парочки примеров модульные тесты.

Для импорта модулей используем Node.js.

Импортируем fs и определяем корневую директорию:

import fs from 'fs'  const rootDir = '../javascript-algorithms/src' 

Для определения того, что мы зашли в директорию, воспользуемся методом isDirectory из модуля fs. Я предпочитаю оборачивать его в функцию, чтобы не писать весь метод:

function isDirectory(filepath) {     return fs.statSync(filepath).isDirectory() } 

Cоздадим функцию «hasTest», принимающую массив строк, проходящую по нему и определяющую наличие тестов. При наличии теста возвращается true, иначе — false:

function hasTest(testDir) {     for (let i = 0; i < testDir.length; i++) {         const filename = testDir[i]         if (filename.endsWith('.test.js')) {             return true         }     }     return false } 

Теперь создадим главную функцию «findEmptyTests», аккумулирующую модули без тестов:

function findEmptyTests(basepath) {     let emptyTests = {}      if (isDirectory(basepath)) {         const dir = fs.readdirSync(basepath)          for (let i = 0; i < dir.length; i++) {             const filename = dir[i]             const filepath = `${basepath}/${filename}`              if (isDirectory(filepath)) {                 if (filename === '__test__') {                     const testDir = fs.readdirSync(filepath)                     if (!hasTest(testDir)) {                         emptyTests[filepath] = createMissingTestsObject(basepath, testDir)                     }                 } else {                     emptyTests = {                         ...emptyTests,                         ...findEmptyTests(filepath)                     }                 }             }         }     }     return emptyTests } 

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

emptyTests = {     ...emptyTests,     ...findEmptyTests(filepath) } 

Это самая важная часть!

Мы начинаем с того, что передаем функции «findEmptyTests» начальную точку (путь файла).

Функция просматривает директории и записывает их имена в массив «dir».

Затем выполняется цикл, в ходе которого проверяется следующее:

1. Если текущая директория называется "__test__", проверяется наличие файлов, имена которых заканчиваются на ".test.js". Если таких файлов нет, информация о модуле помещается в объект «emptyTests».
2. Если текущая директория не __test__, заходим в нее и снова запускаем функцию и т.д.

Наконец, возвращается результат.

Функция «createMissingTestsObject» собирает информацию о пути и директории:

function createMissingTestsObject(str, dir) {     const indexToSrc = str.indexOf('src')     let category = str.substring(indexToSrc + 4)     let subcategory = category.substring(category.indexOf('/') + 1)     subcategory = subcategory.substring(0, subcategory.indexOf('/'))     category = category.substring(0, category.indexOf('/'))      return {         name: str.substring(str.lastIndexOf('/') + 1),         category,         subcategory,         totalFiles: dir.length,         filesList: dir     } } 

Наша программа работает как ожидается — возвращает объект с директориями без тестов!

{     "../javascript-algorithms/src/algorithms/math/fourier-transform/__test__": {         "name": "fourier-transform",         "category": "algorithms",         "subcategory": "math",         "totalFiles": 1,         "filesList": ["FourierTester.js"]     },     "../javascript-algorithms/src/algorithms/sets/cartesian-product/__test__": {         "name": "cartesian-product",         "category": "algorithms",         "subcategory": "sets",         "totalFiles": 0,         "filesList": []     },     "../javascript-algorithms/src/algorithms/sets/combination-sum/__test__": {         "name": "combination-sum",         "category": "algorithms",         "subcategory": "sets",         "totalFiles": 0,         "filesList": []     } } 

Благодарю за внимание. Надеюсь, вы нашли для себя что-то полезное.