Изучение основных строительных блоков рекурсивных функций в JavaScript простым и интуитивно понятным способом.

Поскольку многие из нас, разработчиков, изо всех сил пытаются понять рекурсивные функции, мы избегаем их использования, как ящика Пандоры, и прибегаем к императивному коду (знакомые циклы for и while). ) только для того, чтобы выполнить работу. Это позор, потому что в понимании и написании рекурсивного кода есть много преимуществ, одно из которых может сделать нас лучшими программистами. Этот пост прольет новый свет на рекурсивные функции, разделив их на базовые строительные блоки или каркасы, которые каждый может легко повторно применить при написании других более сложных рекурсивных функций с использованием доступного языка JavaScript.

Рекурсивный length

Взгляните на функцию length, которая вычисляет длину массива, подобного Arr.length, написанного рекурсивным способом:

function length(arr) {
  if (arr.length === 0) {
    return 0;
  } else {
    const t = arr.slice(1, arr.length)
    return 1 + length(t);
  }
}

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

В случае этой функции length мы можем вывести базовый случай как «Если массив пуст, то длина равна 0». Для length имеет смысл возвращать 0, когда arr является пустым массивом. Базовый вариант находится в блоке if.

Может быть немного странно вызывать метод arr.length в коде. В JavaScript нельзя просто утверждать arr === [], чтобы определить пустой массив arr.

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

  1. Индуктивная часть — в этом случае уменьшение arr на единицу в сторону пустого массива и получение указателя на него в соответствии со строкой 5.
  2. Рекурсивная часть — делится на две части:
  • Голова — это то, что мы хотим накопить с течением времени. В этом случае мы хотим прибавлять 1 к счетчику каждый раз, когда мы сталкиваемся с ним, и уменьшать arr на единицу.
  • Хвостовой вызов самого length с уменьшенным массивом в качестве аргумента.

При каждом рекурсивном вызове самого себя length(t) принимает в качестве аргумента массив с одним элементом меньше, а к каждому члену меньше добавляется 1. Индуктивный случай находится в блоке else.

Функция, которая собирает

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

function sSplit(str) {
  if (str === "") {
    // Base case here.
  } else {
    // Inductive case here.
  }
}

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

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

Индуктивная часть

Мы хотим уменьшить строку str бит за битом, чтобы достичь базового случая пустой строки. Это означает «пережевывание» первого символа текущей строки с помощью str.slice(1, str.length) , который разрезает строку от второго символа до конца этой строки, опуская первый символ. Однако в этом случае мы также хотим собрать каждый пропущенный символ, потому что, в конце концов, мы возвращаем массив отдельных символов. Таким образом, мы хотим сохранить первого персонажа для следующей части.

Теперь наша функция выглядит так:

function sSplit(str) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
  }
}

Мы используем причудливое сопоставление с образцом в JavaScript для извлечения первого символа и остальной части строки в одну строку. h теперь хранит первую букву текущего str, а t хранит остальную часть строки за вычетом первой буквы.

Рекурсивная часть

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

Теперь мы модифицируем функцию sSplit, чтобы она принимала массив в качестве дополнительного необязательного аргумента:

function sSplit(str, arr = []) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
  }
}

Теперь мы можем использовать arr в качестве постоянства. В хвостовой части вызов самой функции с str на один символ меньше и arr на один символ больше:

function sSplit(str, arr = []) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
    return sSplit(t, arr.concat([h]));
  }
}

Мы могли бы легко вызвать arr.push(h) перед вызовом sSplit(t, arr), но он изменяет исходный массив, что делает код длиннее и труднее для понимания. arr.concat([h]) возвращает новый массив из двух объединенных массивов, что более функционально, но требует большей производительности.

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

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

Вот наш полный код для sSplit:

function sSplit(str, arr = []) {
  if (str === "") {
    return arr;
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
    return sSplit(t, arr.concat([h]));
  }
}

Резюме…

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

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