Избавьтесь от «запутанности» рекурсией

Вы когда-нибудь смотрели на свои запасы зелий и думали: «Какие разные зелья я могу приготовить из этих ингредиентов?»? Чтобы понять это, вам нужно знать все возможные подмножества ингредиентов, верно?

Что ж, у меня есть для этого заклинание, которого не знает даже величайший Мастер Зелий. Это называется рекурсия.

В разработке программного обеспечения рекурсия – это когда функция вызывает сама себя.

Выполняя домашнюю работу по изучению маглов, я наткнулся на курс MIT Open Courseware «Введение в информатику и программирование на Python» и познакомился с этим небольшим фрагментом мощного рекурсивного кода. Он находит все возможные подмножества данной коллекции (без повторов).

Я адаптировал его здесь, чтобы использовать Typescript и принимать входной массив строк:

function generateSubsets(ingredients: string[]): string[][] {
  if (ingredients.length === 0) {
    return [[]];
  };

  let subsets = generateSubsets(ingredients.slice(0, -1));

  let nextIngredient = ingredients.slice(-1);
  let subsetsUsingNextIngredient = [];

  subsets.forEach((subset) => {
    subsetsUsingNextIngredient.push(subset.concat(nextIngredient));
  });

  return subsets.concat(subsetsUsingNextIngredient);
}

В двух словах, этот код рекурсивно перебирает массив ingredients, каждый раз опуская последний элемент, создавая своего рода стек:

Когда generateSubsets достигает вершины этого стека (где ingredients равно []), он возвращает [[]]. Затем он возвращается вниз по стеку, создавая различные подмножества ингредиентов, прикрепляя последний элемент ingredients в этой области к каждому из предыдущих созданных подмножеств.

Если это не имеет смысла, я не виню вас. Попытка понять этот код действительно поставила меня в тупик (без каламбура), поэтому я разбил его здесь.

Допустим, мы хотим получить все возможные подмножества для следующих ингредиентов:

["unicorn hair", "lacewing fly", "asphodel", "bicorn horn"]

Мы начнем с вызова generateSubsets и передачи этого массива как ingredients.

Далее мы проверим, равна ли длина ingredients 0. Мы знаем, что здесь это не так, поэтому не будем возвращаться к строке 5.

Вместо этого мы перейдем к рекурсивному вызову generateSubsets в строке 8. Здесь мы будем передавать ["unicorn hair", "lacewing fly", "asphodel"] в качестве нашего аргумента, потому что мы делаем поверхностную копию всех элементов текущего массива ingredients, кроме последнего. .

Это возвращает нас к началу функции с ["unicorn hair", "lacewing fly", "asphodel"] в качестве ingredients. Мы продвигаемся вверх по стеку.

Этот шаблон продолжается до тех пор, пока мы не достигнем вершины стека, где ingredients равно [].

На данный момент мы рекурсивно вызвали generateSubsets с аргументом [].

Теперь мы снова проверяем, равна ли длина ingredients 0. На этот раз это так! Поэтому мы возвращаем [[]] в строке 5.

Теперь здесь все становится интереснее.

Этот возврат в строке 5 возвращает обратно на предыдущий уровень стека, где в настоящее время находится ["unicorn hair"] ингредиентов.

Теперь мы начали двигаться вниз по стеку, и теперь subsets равно [[]].

Следующее, что мы делаем, это создаем массив с последним элементом в ingredients и назначаем его nextIngredient. Помните ранее, когда я сказал, что мы собираемся добавить последний ингредиент к каждому из ранее созданных подмножеств? Вот где мы это делаем.

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

Затем мы повторяем наши существующие subsets и создаем новые подмножества, прикрепляя nextIngredient. Итак, на этом этапе стека subsetsUsingNextIngredient становится ["unicorn hair"].

Затем мы объединяем subsets с subsetsUsingNextIngredient и возвращаем следующий массив:

[[], ["unicorn hair"]]

Это возвращает к предыдущему уровню стека, где ingredients в настоящее время равно ["unicorn hair", "lacewing fly"], а subsets теперь равно:

[[], ["unicorn hair"]]

Этот шаблон продолжается до тех пор, пока мы не достигнем первого уровня стека, который снова находится во внешней области видимости, где мы первоначально вызвали generateSubsets с полным списком ["unicorn hair", "lacewing fly", "asphodel", "bicorn horn"] в качестве нашего ingredients.

Мы создадим наши подмножества с ["bicorn horn"] в качестве нашего nextIngredient, заставив subsetsUsingNextIngredient оценивать как

[["bicorn horn"], ["unicorn hair", "bicorn horn"], ["lacewing fly", "bicorn horn"], ["unicorn hair", "lacewing fly", "bicorn horn"], ["asphodel", "bicorn horn"], ["unicorn hair", "asphodel", "bicorn horn"], ["lacewing fly", "asphodel", "bicorn horn"], ["unicorn hair", "lacewing fly", "asphodel", "bicorn horn"]]

И тогда, наконец, generateSubsets вернет все возможные подмножества:

[[], ["unicorn hair"], ["lacewing fly"], ["unicorn hair", "lacewing fly"], ["asphodel"], ["unicorn hair", "asphodel"], ["lacewing fly", "asphodel"], ["unicorn hair", "lacewing fly", "asphodel"], ["bicorn horn"], ["unicorn hair", "bicorn horn"], ["lacewing fly", "bicorn horn"], ["unicorn hair", "lacewing fly", "bicorn horn"], ["asphodel", "bicorn horn"], ["unicorn hair", "asphodel", "bicorn horn"], ["lacewing fly", "asphodel", "bicorn horn"], ["unicorn hair", "lacewing fly", "asphodel", "bicorn horn"]]

Фу! Это заняло некоторое время. Но именно поэтому этот тип рекурсивного кода так эффективен. Он делает так много всего в нескольких строках кода.

Итак, какое зелье на самом деле делают волосы единорога и асфодель 🤔?

Подпишитесь на DDIntel Здесь.

Посетите наш сайт здесь: https://www.datadriveninvestor.com

Присоединяйтесь к нашей сети здесь: https://datadriveninvestor.com/collaborate