Практическое применение рекурсии в JavaScript

Игорь Быков, Frontend Developer в Opticks Security, написал практический гайд по применению рекурсии в JavaScript, без большого O, без чисел Фибоначчи и других скучных академических примеров. Приводим отрывок из его статьи, который демонстрирует как использовать рекурсию при работе с многоуровневыми массивами.

В программировании есть два способа запускать повторяющиеся вычисления — это циклы и рекурсия. Такие циклы как for, while, Array.prototype.map и Array.prototype.forEach по умолчанию внедрены в JavaScript. Но рекурсия — это более гибкая возможность для циклических вычислений. Использовать ее мешают только ментальные барьеры.

Например, применим рекурсию для выравнивания вложенных массивов:

const flatToBase = array => array.reduce(
  (accumulator, value) => accumulator.concat(
    Array.isArray(value) ? flatToBase(value) : value
  ),
  [],
);

flatToBase([[[[[[[ 42 ]]]], 36]]]); // -> [ 42, 36 ]

Для решения этой проблемы в JavaScript есть встроенная функция Array.prototype.flat. Но для выравнивания вложенных массивов неопределенной глубины ее применение считается плохой практикой:

nestedArrays.flat(Infinity);

Цикл + рекурсия

Эти двое не обязательно должны конкурировать друг с другом. Они прекрасно работают вместе!

Допустим мы получаем с сервера следующую структуру:

// Fetched from server

const nestedNumbers = [
  [[0], [[[[[[[1, 2]]]]]]], [3]],
  [[[4], [[5]]], [[[6, 7, 8]]]],
  [9]
];

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

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

const incrementNestedNumbers = (arrayWithNums) => {
  for (let i = 0; i < arrayWithNums.length; i++) {
    if (Array.isArray(arrayWithNums[i])) { // if array
      incrementNestedNumbers(arrayWithNums[i]);
    } else { // if number
      arrayWithNums[i] = arrayWithNums[i] + 1;
    }
  }
};

incrementNestedNumbers(nestedNumbers);

/* nestedNumbers now look like this:
  [[1], [[[[[[[2, 3]]]]]]], [4]],
  [[[5], [[6]]], [[[7, 8, 9]]]],
  [10]
*/

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