Первоначально опубликовано на selftaughttxg.com

Готовитесь ли вы к собеседованию по программированию или хотите узнать о рекурсии, в этой статье разработчик полного стека Даниэль Нагаока учит нас, как написать рекурсивную функцию на JavaScript!

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

Рекурсивная функция JavaScript, представленная в этой статье, состоит всего из нескольких строк кода.

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

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

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

Вот законченная рекурсивная функция JavaScript, описанная в этой статье:

function flattenRecursive(arr) {
    return arr.reduce(
        (consolidated, child) => {
            if (Array.isArray(child)) {
                consolidated.push(...flattenRecursive(child));
            } else {
                consolidated.push(child);
            }
            return consolidated;
        },
        [], 
    );
}
const yay = [1, 2, [3, [4, [5, [6, [[[[[7], [8, 9]]]]]]], 10]]];
  console.log(flattenRecursive(yay));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

О Даниэле Нагаоке

У Дэна есть опыт разработки как Frontend, так и Full Stack. Он окончил Университет Паулиста в Сан-Паулу, Бразилия, со степенью бакалавра компьютерных наук.

Что такое рекурсия

Итак, что такое рекурсия? Веб-документы MDN поясняют: Действие функции, называющей себя рекурсией, используется для решения проблем, содержащих более мелкие подзадачи. Рекурсивная функция может получать два входа: базовый вариант (завершает рекурсию) или рекурсивный вариант (возобновляет рекурсию).

Когда использовать рекурсию

Цитирую Дэн:

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

Мы узнаем больше о его применимости далее в статье.

Как я нашел рекурсивную функцию Дэна

Я познакомился с рекурсивной функцией Дэна, участвуя в ежегодном 24-дневном мероприятии по кодированию Scrimba JavaScriptmas.

Задание 17 дня, Pumpkin’s Prizes, предлагает нам написать функцию, объединяющую вложенные массивы строк или чисел в один массив.

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

Поэтому я был взволнован, когда наткнулся на сообщение Дэна в Discord на JavaScriptmasmas вместе со ссылкой на его элегантное решение:

Изначально у Дэна было всего несколько строк кода без комментариев, объясняющих, что делает строка кода.

Я обратился к Дэну, похвалив его работу, и спросил, не мог бы он подробнее рассказать о своем решении, так как оно принесет значительную пользу другим, изучающим программирование, включая меня!

Он не только добавил комментарии к своему решению, но и Дэн также нашел время, чтобы написать целый раздел статьи в выпуске 3 моей серии статей JavaScriptmasmas 2023.

Тема рекурсии и раздел статьи, который написал Дэн, заслуживали отдельной статьи, которую вы сейчас читаете.

Понимание функции

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

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

Рекурсивная функция Дэна состоит из следующего:

  • Метод уменьшения
  • Функция стрелки
  • операторы if и else
  • isArray метод
  • Метод проталкивания массива
  • Оператор спреда
  • Массив JavaScript

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

Уменьшение массива JavaScript()

В веб-документах MDN поясняется, что метод reduce() является итеративным методом. Он запускает функцию обратного вызова reducer для всех элементов массива в порядке возрастания индекса и накапливает их в одно значение.

const numbers = [1,2,3,4,5];
const numbersReduced = numbers.reduce((total, currentValue) => {
  return total += currentValue;
}, 0);
console.log(numbersReduced);
15

В приведенном выше примере числа 1,2,3,4 и 5 в массиве чисел уменьшаются до значения 15 следующим образом:

1+0 = 1
2+1 = 3
3+3 = 6
4+6 = 10
5+10 = 15

В методе сокращения начальное значение является необязательным. В приведенном выше примере мы устанавливаем начальное значение равным 0.

Понимание того, как установить начальное значение в методе сокращения, важно для рекурсивной функции Дэна; он устанавливает начальное значение в пустой массив.

Функция стрелки

Веб-документы MDN поясняют, что стрелочное функциональное выражение — это компактная альтернатива традиционному функциональному выражению с некоторыми семантическими отличиями и преднамеренными ограничениями в использовании:

  • Стрелочные функции не имеют собственных привязок к this, arguments или super, и их не следует использовать в качестве методов.
  • Стрелочные функции нельзя использовать в качестве конструкторов. Вызов их с помощью new вызывает TypeError. У них также нет доступа к ключевому слову new.target.
  • Стрелочные функции не могут использовать yield внутри своего тела и не могут быть созданы как функции-генераторы.

Стрелочная функция, написанная в рекурсивной функции Дэна, проста, так что не беспокойтесь. Я просто хочу, чтобы вы поняли синтаксис, если вы не знакомы со стрелочными функциями.

Для демонстрации я написал две простые функции приветствия:

function greetOne(name) {
  return "Hello " + name;
}
  console.log(greetOne("Michael"));
"Hello Michael"

Вот та же функция, переписанная как стрелочная:

greetTwo = name => "Hello " + name;
  console.log(greetTwo("Michael"));
"Hello Michael"

Переписав функцию приветствия как функцию со стрелкой, мы устранили следующий синтаксис:

  • функция
  • круглые скобки
  • фигурные скобки
  • возвращаться

Операторы if и else

Утверждение if указывает блок кода для выполнения, если условие истинно, а оператор else указывает блок кода для выполнения, если условие ложно.

В приведенной ниже функции приветствия, если вы передаете имя в качестве параметра, переменная приветствия включает это имя. Если вы не передадите имя в качестве параметра, переменная приветствия будет равна «Привет».

function greet(name) {
  let greeting = "";
  if (name != null) {
    //  Condition is true
    greeting = "Hello, " + name;
  } else {
    //  Condition is false
    greeting = "Hello"
  }
  return greeting;
}  
console.log(greet("Michael"));
"Hello, Michael"
console.log(greet());
"Hello"

Исмассив

Метод JavaScript IsArray проверяет, является ли объект массивом. Если это массив, он возвращает true. Если это не массив, возвращается false.

В этом блоке кода isArray возвращает значение true:

const colors = ["Red", "Yellow", "Green", "Blue"];
let result = Array.isArray(colors);
  console.log(result);
true

В этом блоке кода isArray возвращает false:

const firstName = "Michael";
  console.log(Array.isArray(firstName));
false

Массив JavaScript push()

Метод push() добавляет новые элементы в конец массива.

В приведенном ниже примере мы добавляем цвет «Оранжевый» в массив цветов с помощью метода push.

const colors = ["Red", "Yellow", "Green", "Blue"];
colors.push("Orange");
console.log(colors);
["Red","Yellow","Green","Blue","Orange"]

Оператор спреда

w3schools объясняет, что оператор распространения (…) в JavaScript позволяет нам быстро скопировать весь или часть существующего массива или объекта в другой массив или объект.

В приведенном ниже примере два числовых массива объединяются в один новый числовой массив.

const numberSetOne = [1,2,3,4,5];
const numberSetTwo = [6,7,8,9,10];
const numberSetsCombined = [...numberSetOne, ...numberSetTwo];
console.log(numberSetsCombined);
[1,2,3,4,5,6,7,8,9,10]

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

const numberSetOne = [1,2,3,4,5];
const numberSetTwo = [6,7,8,9,10];
const numberSetOneAndNumberSetTwo = [numberSetOne, numberSetTwo];
console.log(numberSetOneAndNumberSetTwo);
[[1,2,3,4,5],[6,7,8,9,10]]

Массивы JavaScript

Веб-документы MDN говорят нам, что объект Array, как и массивы в других языках программирования, позволяет хранить набор из нескольких элементов под одним именем переменной и имеет члены для выполнения общих операций с массивами.

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

const myArray = [];

Примечание. Массивы не являются константами. w3schools объясняет, что ключевое слово const немного вводит в заблуждение. Оно НЕ определяет константный массив. Он определяет постоянную ссылку на массив. Благодаря этому мы по-прежнему можем изменять элементы константного массива.

Раздел статей Дэна

Теперь, когда мы рассмотрели весь JavaScript, используемый в рекурсивной функции Дэна, пора Дэну научить нас, как ее создать.

Ниже приведен раздел статьи Дэна, ранее публиковавшийся в JavaScriptmas 2022 — Issue 3 на тему рекурсии ⬇

Во-первых, несколько замечаний по методу Array.prototype.reduce(). Это не главная особенность решения, но для новичков она может оказаться весьма полезной, поэтому я предпочел бы остановиться на ней, хотя и вкратце.

Короче говоря, метод сокращения объединяет исходный массив в одно значение, которое может быть практически любым, от string или number до совершенно нового массива или объекта. Для этого он выполняет итерацию по своим дочерним элементам и обрабатывает каждый из них пользовательской функцией — функция обратного вызова редюсера. Редьюсер всегда будет получать данные о текущей итерации в качестве аргументов, наиболее важными из которых являются:

  1. Консолидированное (или «накопленное») значение, которое будет расширено, а затем передано на следующую итерацию;
  2. Текущий дочерний элемент обрабатывается в этой итерации.

Поэтому сам метод сокращения требует:

  1. Функция обратного вызова редуктора, как описано выше;
  2. Начальное состояние для консолидированного значения.

Для практического объяснения вы можете обратиться к этому действительно хорошему видео Моша.

Теперь о фактическом использовании рекурсии.

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

Давайте начнем с того, что уберем кое-что с пути: рекурсия !== зацикливание. Это не так, и если вы используете его для этой цели, то вы просто создаете запутанный код.

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

Почему это применимо в нашем текущем сценарии? Допустим, вам нужно сгладить массив с помощью цикла forloop:

function flatten(arr) {
  const newArray = [];
  for (const item of array) {
    if (Array.isArray(item)) newArray.push(...item);
    else newArray.push(item);
  }
  return newArray;
}
const array = [1, 2, [3, 4]];
// [1, 2, 3, 4];
console.log(flatten(array));

Конечно, это работает, но попробуйте другую, более сложную структуру массива. Скажем:

const ohnoes = [1, 2, [3, [4, 5]]];
// [1, 2, 3, [4, 5]]
console.log(flatten(ohnoes));

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

Однако рекурсивное мышление часто является сложной задачей. Давайте посмотрим на проблему немного ближе:

  • Мы хотим сгладить массив, который, вероятно, будет иметь дочерние массивы;
  • Однако не гарантируется, что дочерние массивы будут сведены сами по себе.

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

  • Функция должна только достигать своего returnвыражения с сглаженным массивом;
  • Путь рекурсии в конечном итоге достигнет нижнего узла структуры — массива без дочерних массивов — и затем вернет его.

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

Теперь осталось собрать нашу рекурсивную функцию:

function flattenRecursive(arr) {
    // loop through the children to see which requires flattening
    return arr.reduce(
        (consolidated, child) => {
            // check if the child is an array itself
            if (Array.isArray(child)) {
                // we need to flatten the array before including its elements in
                // our consolidated array, so we call flattenRecursive recursively
                consolidated.push(...flattenRecursive(child));
            } else {
                // not an array, so just include it in the final array
                consolidated.push(child);
            }
            
            // return the consolidated array
            return consolidated;
        },
        [], // the initial, empty array
    );
}

И теперь мы получаем:

const yay = [1, 2, [3, [4, [5, [6, [[[[[7], [8, 9]]]]]]], 10]]];
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(flattenRecursive(yay));

И это все!

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

- Дэн

Дэн ссылки

🔗 LinkedIn: Дэниел Нагаока

🔗 Ссылка на схватку Дэна: Призы тыквы

Заключение

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

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

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

Подключаемся! Я активен в LinkedIn и Twitter.

Теперь вы лучше понимаете рекурсию? Вас просили рекурсивно решить проблему во время собеседования по программированию? Пожалуйста, поделитесь статьей и прокомментируйте!